oj.uz

Submission #49890

# Submission time Handle Problem Language Result Execution time Memory
49890 2018-06-04T10:57:23 Z tmwilliamlin168 Synchronization (JOI13_synchronization) C++14
100 / 100
 7813 ms 236012 KB 
#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=2, bsts, sti[mxN], mlt[mxN];
vector<pii> av[mxN-1];
vector<int> adj[mxN], cn;
int un, qn, mn;

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) {
	++un;
//	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) {
	++qn;
//	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) {
	++mn;
	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>bsts)
		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;
	sti[c]=1;
	psh(sti[c], 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;
//	}
	for(int i=0; i<=m; ++i)
		upd(1, i, i, i, -1);
	bsts=sts;
	memset(centP, -1, 4*n);
	dfs1(0, -1);
	cd(0, -2);
	while(q--) {
		int ck;
		cin >> ck, --ck;
		cout << ans[ck] << "\n";
	}
//	cout << un << " " << qn << " " << mn;
}

Compilation message

synchronization.cpp: In function 'void upd(int, int, int, int, int, int, int)':
synchronization.cpp:45: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:136: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:165:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<av[e].size()-1; ++i)
                ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5116 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5148 KB Output is correct
4 Correct 7 ms 5308 KB Output is correct
5 Correct 9 ms 5308 KB Output is correct
6 Correct 20 ms 6520 KB Output is correct
7 Correct 307 ms 21928 KB Output is correct
8 Correct 383 ms 22072 KB Output is correct
9 Correct 363 ms 22392 KB Output is correct
10 Correct 4682 ms 211332 KB Output is correct
11 Correct 5537 ms 213560 KB Output is correct
12 Correct 7523 ms 222528 KB Output is correct
13 Correct 1060 ms 222528 KB Output is correct
14 Correct 3691 ms 222528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2338 ms 222528 KB Output is correct
2 Correct 2315 ms 222528 KB Output is correct
3 Correct 3610 ms 222528 KB Output is correct
4 Correct 3901 ms 222528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 222528 KB Output is correct
2 Correct 5 ms 222528 KB Output is correct
3 Correct 6 ms 222528 KB Output is correct
4 Correct 6 ms 222528 KB Output is correct
5 Correct 6 ms 222528 KB Output is correct
6 Correct 24 ms 222528 KB Output is correct
7 Correct 457 ms 222528 KB Output is correct
8 Correct 7538 ms 234700 KB Output is correct
9 Correct 7813 ms 235900 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7159 ms 235984 KB Output is correct
2 Correct 3968 ms 235984 KB Output is correct
3 Correct 4172 ms 235984 KB Output is correct
4 Correct 4172 ms 235984 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 235984 KB Output is correct
2 Correct 6 ms 235984 KB Output is correct
3 Correct 6 ms 235984 KB Output is correct
4 Correct 6 ms 235984 KB Output is correct
5 Correct 21 ms 235984 KB Output is correct
6 Correct 312 ms 235984 KB Output is correct
7 Correct 4689 ms 235984 KB Output is correct
8 Correct 7122 ms 236012 KB Output is correct
9 Correct 954 ms 236012 KB Output is correct
10 Correct 3238 ms 236012 KB Output is correct
11 Correct 2666 ms 236012 KB Output is correct
12 Correct 2636 ms 236012 KB Output is correct
13 Correct 4208 ms 236012 KB Output is correct