Submission #223383

#	Time	Username	Problem	Language	Result	Execution time	Memory
223383		cheeheng	Klasika (COCI20_klasika)	C++14	33 / 110	5057 ms	27024 KiB

klasika

#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[200005][20];
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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44