Submission #339955

#	Time	Username	Problem	Language	Result	Execution time	Memory
339955		Hazem	Klasika (COCI20_klasika)	C++14	33 / 110	2044 ms	33624 KiB

klasika

/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long
const int N = 3e5 + 10;


LL LINF = 100000000000000000;
LL INF = 1000000000;

vector<pair<int,int>>adj[N];
vector<pair<string,pair<int,int>>>queries;
int par[N][30],pr[N],depth[N],tr[N*4],ans,val[N];
set<int>st;
map<int,int>mp;

int lca(int u,int v){

    if(depth[u]<depth[v])swap(u,v);

    for(int i=20;i>=0;i--)
        if(depth[u]-(1<<i)>=depth[v])
            u = par[u][i];
    
    if(u==v)return u;

    for(int i=20;i>=0;i--)
        if(par[u][i]!=par[v][i])
            u = par[u][i],v = par[v][i];

    return par[u][0];
}

void update(int v,int l,int r,int pos){

    if(l==r){
        tr[v]++;
        return ;
    }

    int mid = (l+r)/2;
    if(pos<=mid)update(v*2,l,mid,pos);
    else update(v*2+1,mid+1,r,pos);

    tr[v] = tr[v*2]+tr[v*2+1];
}

int query(int v,int tl,int tr1,int l,int r){

    if(tl>r||tr1<l)return 0;
    
    if(tl>=l&&tr1<=r)
        return tr[v];

    int mid = (tl+tr1)/2;
    return query(v*2,tl,mid,l,r)+query(v*2+1,mid+1,tr1,l,r);
}

void dfs(int i,int pr,int j,int d){

    int cur = i;
    bool q = i==j;
    while(par[cur][0]!=cur)q |= par[cur][0] == j,cur = par[cur][0];

    if(q)ans = max(ans,d);
    for(auto x:adj[i])
        if(x.F!=pr)dfs(x.F,i,j,d^x.S);
}

int get_max(int x){

    int l = 0,r = mp[1<<30];
    
    for(int i=30;i>=0;i--){
        int mid = max(l,mp[1<<i]-1);
        if(x&(1<<i)&&query(1,1,8e5+100,l,mid))r=mid;
        else if(query(1,1,8e5+100,mid+1,r))l = mid+1;
        else r=mid;
    }
    return l;
}

int main()
{
    //freopen("out.txt","w",stdout);
    int q,n = 1;
    scanf("%d",&q);

    par[1][0] = depth[1] = 1;

    while(q--){
        int u,v;
        string s;
        cin>>s>>u>>v;
        queries.push_back({s,{u,v}});
        n++;
        pr[n] = pr[u]^v,depth[n] = depth[u]+1;
        st.insert(pr[n]);
    }

    for(int i=1;i<=30;i++)
        st.insert(1<<i);

    int cnt = 1;
    for(auto x:st)
        val[cnt] = x,mp[x] = cnt++;

    n = 1;
    for(auto x:queries){
        
        string s = x.F;
        int u = x.S.F,v = x.S.S;

        if(s=="Add"){
            adj[u].push_back({++n,v}),adj[n].push_back({u,v});
            par[n][0] = u,pr[n] = pr[u]^v,update(1,1,8e5+100,mp[pr[n]]);
            continue;
        }
        
        else{

            if(queries.size()<=2000){
                ans = 0;
                dfs(u,u,v,0);
                printf("%d\n",ans);
                continue;
            }
            printf("%d\n",val[get_max(pr[u])]);
        }
    }
}       

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~

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