답안 #49898 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49898	2018-06-04T13:27:14 Z	tmwilliamlin168	동기화 (JOI13_synchronization)	C++14	100 / 100	7439 ms	215416 KB

synchronization

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

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

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(int x) {
	int rev=x, count = 0;
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
	putchar_unlocked('\n');
}

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;

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

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) {
	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() {
	n=in(), m=in(), q=in();
	for(int i=0; i<n-1; ++i) {
		x[i]=in()-1, y[i]=in()-1;
		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=in()-1;
		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--)
		out(ans[in()-1]);
}

Compilation message

synchronization.cpp: In function 'void upd(int, int, int, int, int, int, int)':
synchronization.cpp:79: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:149: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:172: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

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	7 ms	5092 KB	Output is correct
3	Correct	7 ms	5128 KB	Output is correct
4	Correct	7 ms	5272 KB	Output is correct
5	Correct	7 ms	5336 KB	Output is correct
6	Correct	19 ms	6424 KB	Output is correct
7	Correct	317 ms	21784 KB	Output is correct
8	Correct	340 ms	21912 KB	Output is correct
9	Correct	397 ms	21912 KB	Output is correct
10	Correct	5488 ms	208648 KB	Output is correct
11	Correct	4710 ms	208648 KB	Output is correct
12	Correct	7120 ms	215076 KB	Output is correct
13	Correct	929 ms	215076 KB	Output is correct
14	Correct	3260 ms	215076 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2541 ms	215076 KB	Output is correct
2	Correct	2626 ms	215076 KB	Output is correct
3	Correct	3464 ms	215076 KB	Output is correct
4	Correct	3706 ms	215076 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	215076 KB	Output is correct
2	Correct	6 ms	215076 KB	Output is correct
3	Correct	9 ms	215076 KB	Output is correct
4	Correct	8 ms	215076 KB	Output is correct
5	Correct	8 ms	215076 KB	Output is correct
6	Correct	32 ms	215076 KB	Output is correct
7	Correct	427 ms	215076 KB	Output is correct
8	Correct	7273 ms	215320 KB	Output is correct
9	Correct	7439 ms	215416 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6920 ms	215416 KB	Output is correct
2	Correct	3440 ms	215416 KB	Output is correct
3	Correct	3525 ms	215416 KB	Output is correct
4	Correct	3507 ms	215416 KB	Output is correct

Subtask #5
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	215416 KB	Output is correct
2	Correct	5 ms	215416 KB	Output is correct
3	Correct	6 ms	215416 KB	Output is correct
4	Correct	7 ms	215416 KB	Output is correct
5	Correct	18 ms	215416 KB	Output is correct
6	Correct	250 ms	215416 KB	Output is correct
7	Correct	5266 ms	215416 KB	Output is correct
8	Correct	6887 ms	215416 KB	Output is correct
9	Correct	938 ms	215416 KB	Output is correct
10	Correct	3138 ms	215416 KB	Output is correct
11	Correct	2905 ms	215416 KB	Output is correct
12	Correct	2638 ms	215416 KB	Output is correct
13	Correct	4139 ms	215416 KB	Output is correct

답안 #49898

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 10.0 / 10.0

Subtask #4 20.0 / 20.0

Subtask #5 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
10.0 / 10.0

Subtask #4
20.0 / 20.0

Subtask #5
40.0 / 40.0