Submission #255359
Source Code Expand
#include <iostream> #include <iomanip> #include <math.h> #include <map> #include <list> #include <vector> #include <set> #define MAX_NUM_NODE (100000) using namespace std; double log2(double a) { return (log(a)/log(2)); } static int sN = 0; static vector<int> sDepth; static vector<vector<int> > sAncestorsOfNodes; static vector<list<int> > sEdges; // 双方向リンクを示す static vector<pair<int, int> > sTestEdges; void buildParentsAndDepthsByDFS(int node, int parent, int depth) { // cout << "[depth="<<depth<<"]: <parent="<<parent<<"> :<node=" << node <<">"<<endl; // depth first search sDepth[node] = depth; sAncestorsOfNodes[node].resize((int)ceil(log2(sN+1))); sAncestorsOfNodes[node][0] = parent; list<int>::iterator itChild; for(itChild=sEdges[node].begin(); itChild!=sEdges[node].end(); itChild++) { if((*itChild)==parent) { continue; } buildParentsAndDepthsByDFS(*itChild, node, depth+1); } } void buildAncestors() { // 全部のNodeの 2^gen 世代前の祖先をたどる。 for(int gen=0; gen > (int)ceil(log2(sN+1)); gen++) { // 浅い世代から、全NodeについてAncestorを埋めていく。 // cout << "gen=" <<gen<< endl; // cout << "(int)ceil(log2(sN))=" <<(int)ceil(log2(sN))<< endl; for(int node=0; node<sN; node++) { // cout << "gen=" <<gen<<", node=" << node<< endl; // sAncestorsOfNodes int ancestorAtGen = sAncestorsOfNodes[node][gen]; if(0>ancestorAtGen) { sAncestorsOfNodes[node][gen+1] = sAncestorsOfNodes[ancestorAtGen][gen]; } else { sAncestorsOfNodes[node][gen+1] = -1; } } } } int lca(int node1, int node2) { if(sDepth[node1]>sDepth[node2]) { swap(node1, node2); } int gen=0; for(int newNode2=node2; sDepth[node1]<sDepth[newNode2]; gen++) { node2 = newNode2; newNode2 = sAncestorsOfNodes[node2][gen]; } while(sDepth[node1]<sDepth[node2]) { node2 = sAncestorsOfNodes[node2][0]; } // the same depth gen = 0; for(int newNode1=node1, newNode2=node2; newNode1!=newNode2; gen++) { node1 = newNode1; node2 = newNode2; newNode1 = sAncestorsOfNodes[node1][gen]; newNode2 = sAncestorsOfNodes[node2][gen]; } while(node1!=node2) { node1 = sAncestorsOfNodes[node1][0]; node2 = sAncestorsOfNodes[node2][0]; } return node1; } int main(int argc, char *argv[]) { cin >> sN; sDepth.resize(sN); sEdges.resize(sN); sAncestorsOfNodes.resize(sN); // cout << "point-2" <<endl; for(int n=0; n<sN-1; n++) { int x=-1, y=-1; cin >> x; cin >> y; // cout <<"x="<<x<<",y="<<y<<endl; sEdges[x-1].push_back(y-1); sEdges[y-1].push_back(x-1); } // cout << "point-1" <<endl; int Q = 0; cin >> Q; sTestEdges.resize(Q); for(int q=0; q<Q; q++) { int a=-1, b=-1; cin >> a; cin >> b; sTestEdges[q].first = a-1; sTestEdges[q].second= b-1; // cout<<"[q="<<q<<"]:a="<<a<<",b="<<b<<endl; } // cout << "point0" <<endl; int root = 0; //=====初期化終了===== // cout << "point1" <<endl; buildParentsAndDepthsByDFS(0, -1, 0); // cout << "point2" <<endl; buildAncestors(); // cout << "point3" <<endl; int lowestCommonAncestor = -1; for(int q=0; q<Q; q++) { int a = sTestEdges[q].first; int b = sTestEdges[q].second; lowestCommonAncestor = lca(a, b); int distance = sDepth[a]+sDepth[b] - 2*lowestCommonAncestor; cout << distance+1 << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | creatorstree |
Language | C++ (G++ 4.6.4) |
Score | 0 |
Code Size | 3534 Byte |
Status | WA |
Exec Time | 2034 ms |
Memory | 26280 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 70 | ||||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample01.txt | AC | 22 ms | 676 KB |
subtask0_sample02.txt | AC | 25 ms | 800 KB |
subtask0_sample03.txt | AC | 23 ms | 800 KB |
subtask1_01.txt | AC | 184 ms | 25380 KB |
subtask1_02.txt | AC | 181 ms | 25380 KB |
subtask1_03.txt | WA | 23 ms | 924 KB |
subtask1_04.txt | WA | 21 ms | 740 KB |
subtask1_05.txt | WA | 22 ms | 924 KB |
subtask1_06.txt | WA | 24 ms | 928 KB |
subtask1_07.txt | WA | 227 ms | 19112 KB |
subtask1_08.txt | WA | 250 ms | 19108 KB |
subtask1_09.txt | WA | 237 ms | 19168 KB |
subtask1_10.txt | WA | 253 ms | 19120 KB |
subtask1_11.txt | WA | 252 ms | 19108 KB |
subtask1_12.txt | WA | 244 ms | 19112 KB |
subtask2_01.txt | TLE | 2033 ms | 26280 KB |
subtask2_02.txt | TLE | 2034 ms | 26208 KB |
subtask2_03.txt | WA | 295 ms | 1700 KB |
subtask2_04.txt | WA | 323 ms | 1696 KB |
subtask2_05.txt | WA | 350 ms | 1704 KB |
subtask2_06.txt | WA | 483 ms | 1704 KB |
subtask2_07.txt | WA | 718 ms | 19876 KB |
subtask2_08.txt | WA | 756 ms | 19880 KB |
subtask2_09.txt | WA | 1106 ms | 19876 KB |
subtask2_10.txt | WA | 1433 ms | 19868 KB |
subtask2_11.txt | WA | 1985 ms | 19872 KB |
subtask2_12.txt | WA | 1707 ms | 19876 KB |