Submission #223381

#TimeUsernameProblemLanguageResultExecution timeMemory
223381cheehengKlasika (COCI20_klasika)C++14
0 / 110
114 ms49400 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> ii; vector<ii> AdjList[200005]; char str[8]; int dist[200005]; int op[200005]; int X[200005]; int Y[200005]; int p[20][200005]; int depth[200005]; int lca(int a, int b){ if(depth[a] < depth[b]){ swap(a, b); } for(int k = 19; k >= 0; k --){ if(p[a][k] == -1){continue;} if(depth[p[a][k]] >= depth[b]){ a = p[a][k]; } } if(a == b){return a;} for(int k = 19; k >= 0; k --){ if(p[a][k] != p[b][k]){ a = p[a][k]; b = p[b][k]; } } return p[a][0]; } bool visited[200005]; void dfs(int u, int p2, int dist1, int d){ if(visited[u]){ return; } dist[u] = dist1; depth[u] = d; visited[u] = true; p[u][0] = p2; for(ii v2: AdjList[u]){ int v = v2.first; if(!visited[v]){ dfs(v, u, dist1^v2.second, d+1); } } } int main(){ int Q; scanf("%d", &Q); int N = 1; for(int i = 0; i < Q; i ++){ memset(str, 0, sizeof(str)); int a, b; scanf(" %s %d %d", str, &a, &b); if(str[0] == 'A'){ op[i] = 0; }else if(str[0] == 'Q'){ op[i] = 1; }else{ throw; } X[i] = a; Y[i] = b; if(op[i] == 0){ N ++; AdjList[a].push_back(ii(N, b)); AdjList[N].push_back(ii(a, b)); } } memset(p, -1, sizeof(p)); memset(visited, 0, sizeof(visited)); dfs(1, -1, 0, 0); for(int k = 1; k <= 19; k ++){ for(int i = 1; i <= N; i ++){ if(p[i][k-1] == -1){ p[i][k] = -1; }else{ p[i][k] = p[p[i][k-1]][k-1]; } } } int m = 1; for(int i = 0; i < Q; i ++){ if(op[i] == 0){ m ++; }else{ int ans = 0; //printf("m=%d, X[i]=%d, Y[i]=%d\n", m, X[i], Y[i]); for(int j = 1; j <= m; j ++){ //printf("lca(%d, %d)=%d\n", Y[i], j, lca(Y[i], j)); if(lca(Y[i], j) == Y[i]){ //printf("%d and %d considered\n", j, X[i]); ans = max(ans, dist[X[i]]^dist[j]); } } printf("%d\n", ans); } } return 0; }

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
klasika.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s %d %d", str, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...