Submission #504104

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
504104	2022-01-09T20:10:26 Z	inksamurai	Deblo (COCI18_deblo)	C++17	45 / 90	1000 ms	34448 KB

deblo

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _34raRxL ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;

void print(){
	cout<<"\n";
}
template<class te,class ...ti>
void print(const te&v, const ti&...nv) { 
	cout<<v;
	if(sizeof...(nv)){
		cout<<" ";
		print(nv...);
	}
}

using tpii=pair<int,pair<int,int>>;
using pii=pair<int,int>;
using vi=vector<int>;
using vll=vector<long long>;


struct treelca{
	int n;
	int timer=0;
	vec(vi) adj;
	vi tin,tout,tour,tourid;
	vi segtree;
	vi depth;
	treelca(int m,int root,vec(vi) neadj){
		init(m,root,neadj);
	}
	void init(int m,int root,vec(vi) neadj){
		n=m;
		tin.clear();
		tout.clear();
		tour.clear();
		tourid.clear();
		depth.clear();
		tin.resize(n,0);
		tout.resize(n,0);
		tourid.resize(n,0);
		depth.resize(n,0);
		adj=neadj;
		dfs(root,-1);
		segtree.resize(4*sz(tour));
		build(1,0,sz(tour)-1);
	}
	void dfs(int v,int par){
		tour.pb(v);
		tourid[v]=sz(tour)-1;
		tin[v]=timer++;
		for(auto u : adj[v]){
			if(u==par) continue;
			depth[u]=depth[v]+1;
			dfs(u,v);
			tour.pb(v);
		}
		tout[v]=timer++;
	}
	void build(int node,int l,int r){
		if(l==r){
			segtree[node]=tour[l];
		}else{
			int m=(l+r)>>1;
			build(node*2,l,m);
			build(node*2+1,m+1,r);
			segtree[node]=(tin[segtree[node*2]]<tin[segtree[node*2+1]]?segtree[node*2]:segtree[node*2+1]);
		}
	}
	int query(int node,int l,int r,int _l,int _r){
		if(l>_r or r<_l) return -1;
		if(l>=_l and r<=_r) return segtree[node];
		int m=(l+r)>>1;
		int vl=query(node*2,l,m,_l,_r);
		int vr=query(node*2+1,m+1,r,_l,_r);
		if(min(vl,vr)==-1) return max(vl,vr);
		return (tin[vl]<tin[vr]?vl:vr);
	}
	int ancestor(int from,int to){
		int tinfrom=tin[from],tinto=tin[to];
		if(tinfrom>tinto) swap(tinfrom,tinto);
		return query(1,0,sz(tour)-1,tinfrom,tinto);
	}
	int dist(int u,int v){
		return depth[u]+depth[v]-depth[ancestor(u,v)]*2;
	}
};


void slv(){
	int n;
	cin>>n;
	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	vec(vi) adj(n);
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u--,v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vi pxor(n,0);
	auto dfs=[&](auto self,int v,int par)->void{
		if(par!=-1){
			pxor[v]=pxor[par];
		}
		pxor[v]^=a[v];
		for(auto u : adj[v]){
			if(u!=par){
				self(self,u,v);
			}
		}
	};
	dfs(dfs,0,-1);
	treelca lca(n,0,adj);
	ll ans=0;
	rep(v,n){
		crep(u,v,n){
			ans+=(pxor[v]^pxor[u]^a[lca.ancestor(u,v)]);
		}
	}
	print(ans,"\n");
}

int main(){
_34raRxL;
	int t=1;
	// cin>>t;
	slv();
//	
	return 0;
}

Compilation message

deblo.cpp: In function 'int main()':
deblo.cpp:142:6: warning: unused variable 't' [-Wunused-variable]
  142 |  int t=1;
      |      ^

Subtask #1

45.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	3 ms	368 KB	Output is correct
4	Correct	53 ms	616 KB	Output is correct
5	Correct	70 ms	596 KB	Output is correct
6	Execution timed out	1054 ms	34448 KB	Time limit exceeded
7	Execution timed out	1039 ms	34420 KB	Time limit exceeded
8	Execution timed out	1098 ms	31208 KB	Time limit exceeded
9	Execution timed out	1089 ms	30884 KB	Time limit exceeded
10	Execution timed out	1050 ms	30628 KB	Time limit exceeded