Submission #49886

#	Time	Username	Problem	Language	Result	Execution time	Memory
49886		tmwilliamlin168	Synchronization (JOI13_synchronization)	C++14	0 / 100	8090 ms	217780 KiB

synchronization

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

#define pii pair<int, int>
#define fi first
#define se second

const int mxN=1e5, mxM=2e5;
int n, m, q, x[mxN-1], y[mxN-1], lb[mxN-1], ans[mxN], centP[mxN], sz[mxN], rt1, sts=1, sti[mxN], mlt[mxN];
vector<pii> av[mxN-1];
vector<int> adj[mxN], cn;

struct node {
	bool lz1;
	int lz2, v, lc, rc;
} st[2*18*(2*mxN+mxM/2)+1]; //2 nodes per layer * logn=18 layers * total updates

inline void psh(int &sti, int v=0, bool x1=0, int x2=0) {
	int lsti=sti;
	if(!sti||st[sti].v!=v) {
		sti=sts++;
		st[sti].v=v;
		if(lsti) {
			st[sti].lc=st[lsti].lc, st[sti].rc=st[lsti].rc;
			st[sti].lz1=st[lsti].lz1, st[sti].lz2=st[lsti].lz2;
		}
	}
	if(x1)
		st[sti].lz1=1, st[sti].lz2=0;
	st[sti].lz2+=x2;
}

void upd(int sti, int l1, int r1, int x, int v=0, int l2=0, int r2=m) {
//	cout << "upd " << sti << " " << l1 << " " << r1 << " " << x << " " << v << " " << l2 << " " << r2 << endl;
	if(l1>r1)
		return;
	if(l1<=l2&&r2<=r1) {
		st[sti].lz1=1, st[sti].lz2=x;
		return;
	}
	psh(st[sti].lc, v, st[sti].lz1, st[sti].lz2);
	psh(st[sti].rc, v, st[sti].lz1, st[sti].lz2);
	st[sti].lz1=st[sti].lz2=0;
	int m2=(l2+r2)/2;
	if(l1<=m2)
		upd(st[sti].lc, l1, r1, x, v, l2, m2);
	if(m2<r1)
		upd(st[sti].rc, l1, r1, x, v, m2+1, r2);
}

int qry(int sti, int l1, int l2=0, int r2=m) {
//	cout << "qry " << sti << " " << l1 << " " << l2 << " " << r2 << endl;
	if(!sti)
		return 0;
	if(st[sti].lz1)
		return st[sti].lz2;
	int m2=(l2+r2)/2;
	return st[sti].lz2+(l1<=m2?qry(st[sti].lc, l1, l2, m2):qry(st[sti].rc, l1, m2+1, r2));
}

void mrg(int &sti1, int sti2) {
	if(!sti1||!sti2) {
		sti1^=sti2;
		return;
	}
	st[sti1].lz2+=st[sti2].lz2;
	if(st[sti2].lz1)
		return;
	if(st[sti1].lz1) {
		st[sti1].lz1=0;
		st[sti1].lc=st[sti2].lc, st[sti1].rc=st[sti2].rc;
		return;
	}
	mrg(st[sti1].lc, st[sti2].lc);
	mrg(st[sti1].rc, st[sti2].rc);
}

inline void clst() {
	while(sts>1)
		st[--sts]={};
	for(int cni : cn)
		sti[cni]=0;
}

void pst(int u, int d=-1) {
	if(d==-1) {
		cout << "pst " << u << endl;
		u=sti[u], d=0;
	}
	if(!u)
		return;
	for(int i=0; i<d; ++i)
		cout << ' ';
	cout << "sti " << u << " lz " << st[u].lz1 << " " << st[u].lz2 << " v " << st[u].v << " c " << st[u].lc << " " << st[u].rc << endl;
	pst(st[u].lc, d+1);
	pst(st[u].rc, d+1);
}

void dfs1(int u, int p) {
	sz[u]=1;
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
		dfs1(v, u);
		sz[u]+=sz[v];
	}
}

int dfs2(int u, int p, int szr) {
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v!=p&&centP[v]==-1&&sz[v]>szr/2)
			return dfs2(v, u, szr);
	}
	return u;
}

void dfs3(int u, int p) {
//	cout << "d3 " << u << " " << p << endl;
	cn.push_back(u);
	mlt[u]=qry(sti[u], m);
//	cout << "d32" << endl;
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
//		cout << "d33 " << v << endl;
		if(v==p||centP[v]!=-1)
			continue;
		sti[v]=sti[u];
		psh(sti[v], v);
//		cout << "d34" << endl;
		for(int i=0; i<av[e].size()-1; ++i)
			/*cout << "d35 " << i << endl, */upd(sti[v], av[e][i].se+1, av[e][i+1].fi-1, qry(sti[v], av[e][i].se), v);
		dfs3(v, u);
//		cout << "d36" << endl;
	}
}

void dfs5(int u, int p) {
//	cout << "d5 " << u << endl;
	ans[u]-=qry(sti[rt1], mlt[u]);
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v!=p&&centP[v]==-1)
			dfs5(v, u);
	}
}

void dfs4(int u, int p, int fav) {
//	cout << "d4 " << u << endl;
	psh(sti[u]);
	upd(sti[u], fav, m, 1);
//	cout << "d42" << endl;
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
//		cout << "d43 " << v << endl;
		dfs4(v, u, av[e][1].fi);
//		cout << "d44 " << endl;
		for(int i=0; i<av[e].size()-1; ++i)
			upd(sti[v], av[e][i].se+1, av[e][i+1].fi-1, qry(sti[v], av[e][i].se));
		if(p==-1) {
			rt1=v;
			dfs5(v, u);
		}
//		pst(v), pst(u);
		mrg(sti[u], sti[v]);
//		cout << "d47" << endl;
	}
}

void cd(int u, int p) {
//	cout << "cd " << u << " " << p << endl;
	int c=dfs2(u, -1, sz[u]);
//	cout << "hi1" << endl;
	centP[c]=p;
	dfs1(c, -1);
//	cout << "hi2" << endl;
	psh(sti[c], c);
	for(int i=0; i<=m; ++i)
		upd(sti[c], i, i, i, c);
//	cout << "hi3" << endl;
	dfs3(c, -1);
//	cout << "hi4" << endl;
	clst();
	dfs4(c, -1, 1);
//	cout << "hi5" << endl;
//	pst(c);
	for(int cni : cn)
		ans[cni]+=qry(sti[c], mlt[cni]);//, cout << cni << " mlt " << mlt[cni] << " sti " << sti[cni] << " ans " << ans[cni] << endl;
	ans[c]+=!mlt[c];
	clst();
//	cout << "hi6" << endl;
	cn.clear();
	for(int e : adj[c]) {
		int v=c^x[e]^y[e];
		if(centP[v]==-1)
			cd(v, c);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	for(int i=0; i<n-1; ++i) {
		cin >> x[i] >> y[i], --x[i], --y[i];
		adj[x[i]].push_back(i);
		adj[y[i]].push_back(i);
		av[i].push_back({0, 0});
	}
	for(int i=1; i<=m; ++i) {
		int dj;
		cin >> dj, --dj;
		if(lb[dj]) {
			av[dj].push_back({lb[dj], i-1});
			lb[dj]=0;
		} else
			lb[dj]=i;
	}
	for(int i=0; i<n-1; ++i)
		av[i].push_back({lb[i]?lb[i]:m+1, m+1});
//	for(int i=0; i<n-1; ++i) {
//		cout << "e " << x[i] << " " << y[i] << endl;
//		for(pii p : av[i])
//			cout << p.fi << " " << p.se << endl;
//	}
	memset(centP, -1, 4*n);
	dfs1(0, -1);
	cd(0, -2);
	while(q--) {
		int ck;
		cin >> ck, --ck;
		cout << ans[ck] << "\n";
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'void upd(int, int, int, int, int, int, int)':
synchronization.cpp:43:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  st[sti].lz1=st[sti].lz2=0;
              ~~~~~~~~~~~^~
synchronization.cpp: In function 'void dfs3(int, int)':
synchronization.cpp:132:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<av[e].size()-1; ++i)
                ~^~~~~~~~~~~~~~~
synchronization.cpp: In function 'void dfs4(int, int, int)':
synchronization.cpp:161:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<av[e].size()-1; ++i)
                ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40