| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 105838 | Pro_ktmr | City (JOI17_city) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}