oj.uz

Submission #56288

# Submission time Handle Problem Language Result Execution time Memory
56288 2018-07-11T02:15:34 Z tmwilliamlin168 Synchronization (JOI13_synchronization) C++14
100 / 100
 7891 ms 256292 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], dj, ck;
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)+2*mxM]; //2 nodes per layer * logn=18 layers * total updates + max nodes in a segtree

__attribute__((always_inline)) void psh(int &sti, int v=0, bool x1=0, int x2=0) {
	if(!sti||st[sti].v!=v) {
		st[sts]=st[sti];
		st[sts].v=v;
		sti=sts++;
	}
	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) {
	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) {
	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>bsts)
		st[--sts]={};
	for(int cni : cn)
		sti[cni]=0;
}

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) {
	cn.push_back(u);
	mlt[u]=qry(sti[u], m);
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
		sti[v]=sti[u];
		psh(sti[v], v);
		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), v);
		dfs3(v, u);
	}
}

void dfs5(int u, int p) {
	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) {
	psh(sti[u]);
	upd(sti[u], 1, m, 1);
	for(int e : adj[u]) {
		int v=u^x[e]^y[e];
		if(v==p||centP[v]!=-1)
			continue;
		dfs4(v, u);
		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);
		}
		mrg(sti[u], sti[v]);
	}
}

void cd(int u, int p) {
	int c=dfs2(u, -1, sz[u]);
	centP[c]=p;
	dfs1(c, -1);
	sti[c]=1;
	psh(sti[c], c);
	dfs3(c, -1);
	clst();
	dfs4(c, -1);
	for(int cni : cn)
		ans[cni]+=qry(sti[c], mlt[cni]);
	ans[c]+=!mlt[c];
	clst();
	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) {
		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<=m; ++i)
		upd(1, i, i, i, -1);
	bsts=sts;
	memset(centP, -1, 4*n);
	dfs1(0, -1);
	cd(0, -2);
	while(q--) {
		cin >> ck, --ck;
		cout << ans[ck] << "\n";
	}
}

Compilation message

synchronization.cpp: In function 'void upd(int, int, int, int, int, int, int)':
synchronization.cpp:38: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:108: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)':
synchronization.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<av[e].size()-1; ++i)
                ~^~~~~~~~~~~~~~~
synchronization.cpp: At global scope:
synchronization.cpp:18:37: warning: always_inline function might not be inlinable [-Wattributes]
 __attribute__((always_inline)) void psh(int &sti, int v=0, bool x1=0, int x2=0) {
                                     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5080 KB Output is correct
2 Correct 7 ms 5104 KB Output is correct
3 Correct 6 ms 5216 KB Output is correct
4 Correct 8 ms 5240 KB Output is correct
5 Correct 8 ms 5476 KB Output is correct
6 Correct 25 ms 6536 KB Output is correct
7 Correct 308 ms 22220 KB Output is correct
8 Correct 333 ms 22528 KB Output is correct
9 Correct 319 ms 22832 KB Output is correct
10 Correct 5756 ms 211488 KB Output is correct
11 Correct 5584 ms 213936 KB Output is correct
12 Correct 7891 ms 222908 KB Output is correct
13 Correct 938 ms 222908 KB Output is correct
14 Correct 3534 ms 222908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2548 ms 222908 KB Output is correct
2 Correct 2569 ms 222908 KB Output is correct
3 Correct 3763 ms 222908 KB Output is correct
4 Correct 3551 ms 222908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 222908 KB Output is correct
2 Correct 6 ms 222908 KB Output is correct
3 Correct 8 ms 222908 KB Output is correct
4 Correct 7 ms 222908 KB Output is correct
5 Correct 8 ms 222908 KB Output is correct
6 Correct 35 ms 222908 KB Output is correct
7 Correct 439 ms 222908 KB Output is correct
8 Correct 7059 ms 237484 KB Output is correct
9 Correct 6996 ms 240336 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7786 ms 243256 KB Output is correct
2 Correct 3764 ms 243256 KB Output is correct
3 Correct 3959 ms 243256 KB Output is correct
4 Correct 3647 ms 243256 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 243256 KB Output is correct
2 Correct 7 ms 243256 KB Output is correct
3 Correct 7 ms 243256 KB Output is correct
4 Correct 10 ms 243256 KB Output is correct
5 Correct 21 ms 243256 KB Output is correct
6 Correct 317 ms 243256 KB Output is correct
7 Correct 5435 ms 247096 KB Output is correct
8 Correct 7234 ms 256292 KB Output is correct
9 Correct 1000 ms 256292 KB Output is correct
10 Correct 3351 ms 256292 KB Output is correct
11 Correct 2876 ms 256292 KB Output is correct
12 Correct 2655 ms 256292 KB Output is correct
13 Correct 3827 ms 256292 KB Output is correct