# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
105838 | 2019-04-15T10:30:04 Z | Pro_ktmr | City (JOI17_city) | C++14 | 0 ms | 0 KB |
#include"bits/stdc++.h" using namespace std; #define LL long long #define PB push_back #define MP make_pair #include"City_lib.h" bool already[250000] = {}; vector<int> edge[250000]; LL c = 0; LL dfs_order[250000]; LL pos[2500000]; void DFS(int now){ already[now] = true; dfs_order[now] = c; c++; for(int i=0; i<edge[now].size(); i++){ if(already[edge[now][i]]) continue; DFS(edge[now][i]); } pos[now] = c; } void Encode(int N, int A[], int B[]){ for(int i=0; i<N-1; i++){ edge[A[i]].PB(B[i]); edge[B[i]].PB(A[i]); } DFS(0); for(int i=0; i<N; i++){ LL tmp = dfs_order[i] << 18; tmp += pos[i]; Code(i, tmp); } } void InitDevice(){ } int Answer(long long S, long long T){ LL x = S >> 18; LL y = T >> 18; LL posX = S % (1<<18); LL posY = T % (1<<18); if(x == 0) return 1; if(y == 0) return 0; if(x < y && posY <= posX) return 1; if(y < x && posX <= posY) return 0; return 2; }