Submission #223431

#	Time	Username	Problem	Language	Result	Execution time	Memory
223431		jamielim	Klasika (COCI20_klasika)	C++14	33 / 110	5076 ms	35960 KiB

klasika

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

const int MAXN=200005;
int n=1,q;
pair<int,pair<int,int> > qu[MAXN];
vector<pair<int,int> > adj[MAXN];

int sub[MAXN];
int depth[MAXN];
int heavy[MAXN];
int pos[MAXN];
int head[MAXN];
int par[MAXN][20];
int cur=1;
 
struct node{
	int s,e,m;long long v,lazy;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;v=lazy=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void laze(){
		if(s==e){v^=lazy;lazy=0;return;}
		v^=lazy;
		l->lazy+=lazy;r->lazy+=lazy;
		lazy=0;return;
	}
	void upd(int x,int y,int nv){
		//printf("u %d %d\n",x,y);
		if(x>y)return;
		if((s==x&&e==y)||s==e){
			lazy^=nv;laze();return;
		}
		if(y<=m)l->upd(x,y,nv);
		else if(x>m)r->upd(x,y,nv);
		else{l->upd(x,m,nv);r->upd(m+1,y,nv);}
		laze();
		v=l->v^r->v;
	}
	long long qry(int x,int y){
		//printf("q %d %d\n",x,y);
		if(x>y)return 0;
		laze();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return l->qry(x,m)^r->qry(m+1,y);
	}
}*root;
 
void dfs(int x,int p){
	sub[x]=1;par[x][0]=p;int maxc=0;
	for(int i=0;i<(int)adj[x].size();i++){
		if(adj[x][i].first!=p){
			depth[adj[x][i].first]=depth[x]+1;
			dfs(adj[x][i].first,x);
			sub[x]+=sub[adj[x][i].first];
			if(sub[adj[x][i].first]>maxc){maxc=sub[adj[x][i].first];heavy[x]=adj[x][i].first;}
		}
	}
}
void dcmp(int x,int h){
	head[x]=h;pos[x]=cur++;
	if(heavy[x]!=-1)dcmp(heavy[x],h);
	for(int i=0;i<(int)adj[x].size();i++){
		if(heavy[x]==adj[x][i].first)continue;
		if(par[x][0]==adj[x][i].first)continue;
		dcmp(adj[x][i].first,adj[x][i].first);
	}
}
void upd(int a,int b,int nv){
	//printf("%d %d\n",a,b);
	if(depth[a]>depth[b])swap(a,b);
	for(;head[a]!=head[b];b=par[head[b]][0]){
		if(depth[head[a]]>depth[head[b]])swap(a,b);
		root->upd(pos[head[b]],pos[b],nv);
	}
	if(depth[a]>depth[b])swap(a,b);
	root->upd(pos[a]+1,pos[b],nv);
}
int qry(int a,int b){
	int res=0;
	if(depth[a]>depth[b])swap(a,b);
	for(;head[a]!=head[b];b=par[head[b]][0]){
		if(depth[head[a]]>depth[head[b]])swap(a,b);
		res^=root->qry(pos[head[b]],pos[b]);
	}
	if(depth[a]>depth[b])swap(a,b);
	res^=root->qry(pos[a]+1,pos[b]);
	return res;
}
int main(){
	scanf("%d",&q);
	char op[15];int a,b;
	for(int i=0;i<q;i++){
		scanf("%s%d%d",op,&a,&b);
		if(op[0]=='A'){
			n++;
			qu[i]=make_pair(n,make_pair(a,b));
			adj[n].push_back(make_pair(a,b));
			adj[a].push_back(make_pair(n,b));
		}else qu[i]=make_pair(-1,make_pair(a,b));
	}
	root=new node(0,n);
	memset(heavy,-1,sizeof(heavy));memset(par,-1,sizeof(par));
	dfs(1,-1);
	dcmp(1,1);
	for(int i=0;i<q;i++){
		if(qu[i].first<0){
			int ans=0;
			for(int j=1;j<=n;j++){
				if(pos[j]>=pos[qu[i].second.second]&&pos[j]<pos[qu[i].second.second]+sub[qu[i].second.second]){
					ans=max(ans,qry(qu[i].second.first,j));
				}
			}
			printf("%d\n",ans);
		}else{
			upd(qu[i].second.first,qu[i].first,qu[i].second.second);
		}
	}
}

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
klasika.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%d",op,&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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