QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225683#1699. The Cow Gatheringpaul2008100 ✓71ms36464kbC++141.9kb2023-10-24 22:59:072023-10-24 22:59:07

Judging History

你现在查看的是最新测评结果

  • [2023-10-24 22:59:07]
  • 评测
  • 测评结果:100
  • 用时:71ms
  • 内存:36464kb
  • [2023-10-24 22:59:07]
  • 提交

answer

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

const int N=2e5+5;

vector <int> g[N];
int q[N],ind[N],head[N],nex[N],to[N],a[N],b[N],indx,n,m;
int dfsn[N],sz[N],dep[N],point[N],fa[N][20],cnt;

void dfs(int x)
{
	dfsn[x]=++cnt,sz[x]=1,point[cnt]=x;
	for(int i=1;i<20;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];

	for(auto to:g[x])
		if(to!=fa[x][0])
			fa[to][0]=x, dep[to]=dep[x]+1, dfs(to), sz[x] += sz[to];
}

int kthfa(int x,int k)
{
	for(int i=19;i>=0;i--)
		if(k>=1<<i)
			x=fa[x][i], k -= 1<<i;
	return x;
}

int add[N];

void cover(int l,int r,int k)
{
	add[l]+=k,add[r+1]-=k;
}

void add_edge(int x,int y)
{
	indx++;
	nex[indx]=head[x];
	to[indx]=y;
	ind[y]++;
	head[x]=indx;
}

void dfs(int x,int fa)
{
	for(auto to:g[x])
	{
		if(to==fa)
			continue;

		add_edge(to,x);
		dfs(to,x);
	}
}

bool topsort()
{
	int l=1,r=0;
	for(int i=1;i<=n;i++)
		if(ind[i]==0)
			q[++r]=i;

	while(l<=r)
	{
		int x=q[l++];
		for(int i=head[x];i;i=nex[i])
		{
			int y=to[i];
			ind[y]--;
			if(ind[y]==0)
				q[++r]=y;
		}
	}

	return r==n;
}

bool check(int point)
{
	dfs(point,-1);
	return topsort();
}

int main()
{
	cin >> n >> m;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	dep[1]=1, dfs(1);

	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		add_edge(a,b);
		if(kthfa(b,dep[b]-dep[a])==a)
		{
			int p=kthfa(b,dep[b]-dep[a]-1);
			cover(1,n,1);
			cover(dfsn[p],dfsn[p]+sz[p]-1,-1);
		}
		else
			cover(dfsn[a],dfsn[a]+sz[a]-1,1);
	}

	for(int i=1;i<=n;i++)
		add[i] += add[i-1];

	int p=0;
	for(int i=1;i<=n;i++)
		if(add[i]==0)
			p=i;

	if(check(point[p]))
	{
		for(int i=1;i<=n;i++)
			if(add[dfsn[i]])
				printf("0\n");
			else
				printf("1\n");
	}
	else
	{
		for(int i=1;i<=n;i++)
			printf("0\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5.88235
Accepted
time: 4ms
memory: 15032kb

input:

5 1
1 2
2 3
3 4
4 5
2 4

output:

0
0
1
1
1

result:

ok 5 lines

Test #2:

score: 5.88235
Accepted
time: 58ms
memory: 29764kb

input:

100000 100000
26925 40810
33785 40810
79724 26925
58114 33785
82120 58114
73434 82120
51827 79724
11823 40810
44846 73434
27385 40810
59892 79724
14931 82120
92201 40810
93160 14931
98031 93160
47365 58114
56630 14931
43532 14931
75960 11823
85928 33785
93902 92201
86227 51827
43737 51827
23165 8592...

output:

0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #3:

score: 5.88235
Accepted
time: 53ms
memory: 28876kb

input:

100000 100000
61436 39109
28482 39109
13074 39109
45587 39109
19584 28482
90325 45587
69113 90325
16682 28482
16999 69113
72138 19584
53448 19584
75504 16682
11506 69113
46782 11506
55008 11506
97103 69113
51136 72138
33729 69113
30516 61436
33145 16999
24875 55008
54464 28482
92666 16682
25607 9710...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #4:

score: 5.88235
Accepted
time: 71ms
memory: 35068kb

input:

100000 100000
99345 63067
36429 99345
87889 36429
50024 87889
25211 50024
99537 25211
65313 99537
8215 65313
60250 8215
38288 60250
79066 38288
67497 79066
3650 67497
64566 3650
4810 64566
17690 4810
24656 17690
29471 24656
50219 29471
45804 50219
4297 45804
94864 4297
74013 94864
2019 74013
36170 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #5:

score: 5.88235
Accepted
time: 55ms
memory: 31288kb

input:

100000 100000
82625 75792
97136 82625
72263 82625
42229 75792
21439 82625
27733 42229
76957 72263
21939 21439
87366 97136
33524 87366
71890 21439
83692 76957
60907 76957
58800 21939
19418 76957
28170 42229
21266 87366
80805 33524
24356 21266
4543 83692
38497 76957
64162 27733
89170 21266
26538 80805...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #6:

score: 5.88235
Accepted
time: 56ms
memory: 30656kb

input:

100000 100000
46400 61120
89967 46400
31442 46400
65113 46400
25735 61120
21338 65113
46168 61120
23530 46168
69042 23530
80686 31442
91130 21338
62429 65113
83742 21338
89547 69042
5830 46168
80043 83742
15330 91130
92323 91130
6526 5830
64689 80043
16771 80043
42653 64689
61194 15330
11881 64689
2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #7:

score: 5.88235
Accepted
time: 52ms
memory: 29820kb

input:

100000 100000
18500 42941
60146 18500
53199 60146
86535 42941
50616 86535
73050 42941
94576 42941
96078 42941
15664 42941
52292 18500
51974 94576
56912 53199
10438 96078
13129 10438
88412 60146
64130 53199
71149 18500
26231 15664
46013 42941
26420 18500
48538 60146
36815 96078
7334 60146
82086 73050...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #8:

score: 5.88235
Accepted
time: 55ms
memory: 31744kb

input:

100000 100000
4814 25398
15158 25398
35659 4814
48072 4814
70716 15158
32279 15158
70859 4814
29453 70716
28165 70859
64536 32279
62334 29453
65784 64536
58935 4814
44629 58935
41097 58935
53405 41097
53997 62334
7937 15158
82362 29453
34552 62334
92434 48072
30690 82362
25115 48072
61129 29453
6620...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #9:

score: 5.88235
Accepted
time: 0ms
memory: 16748kb

input:

4 3
1 2
1 3
1 4
2 3
3 4
4 2

output:

0
0
0
0

result:

ok 4 lines

Test #10:

score: 5.88235
Accepted
time: 2ms
memory: 17320kb

input:

3000 3000
2481 972
2488 972
480 972
350 2481
2921 350
2237 2481
2757 972
2076 2757
1428 2076
172 350
349 172
634 2757
81 349
2504 480
388 972
1151 81
2649 172
743 349
2136 2921
1792 2481
937 480
116 1792
2638 2504
511 972
2678 634
50 2678
1656 349
1187 511
1478 1656
2503 2921
2096 388
2072 1656
1645...

output:

0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
1
0
1
1
1
0
1
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3000 lines

Test #11:

score: 5.88235
Accepted
time: 4ms
memory: 16468kb

input:

3000 3000
2040 1722
1525 2040
2005 2040
2790 2005
170 1525
402 2005
2053 1722
265 2005
1652 402
1567 265
1140 170
1653 2040
1420 1652
1598 1420
1994 170
2564 2040
2049 265
2289 265
1727 1567
777 402
1115 2564
2296 2564
2390 1652
2748 1598
653 1525
1730 1115
2562 2564
263 1598
407 2748
2535 1653
1849...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 3000 lines

Test #12:

score: 5.88235
Accepted
time: 46ms
memory: 29272kb

input:

100000 100000
79234 6465
4822 79234
79876 6465
47233 6465
70148 47233
27031 47233
30271 79876
22720 27031
86717 22720
43586 79234
63968 47233
67479 6465
66830 70148
86550 47233
50935 67479
84175 79876
52137 79234
45528 84175
75583 30271
45424 47233
86741 63968
33603 43586
20776 70148
35389 86741
665...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #13:

score: 5.88235
Accepted
time: 52ms
memory: 29504kb

input:

100000 100000
38864 82575
55487 82575
50208 82575
17635 38864
40864 82575
43070 55487
82331 82575
37387 40864
79930 82331
15985 82331
55120 55487
91853 79930
65787 40864
1909 40864
75614 82575
27910 15985
15047 50208
51111 82575
50261 43070
9508 75614
35996 43070
97407 91853
22915 51111
46844 35996
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #14:

score: 5.88235
Accepted
time: 58ms
memory: 29184kb

input:

100000 100000
57056 75294
80008 75294
28063 75294
34018 80008
8771 34018
89313 57056
20310 57056
20981 8771
15249 8771
67365 20310
76164 28063
55531 15249
20505 15249
65964 20981
7230 8771
97444 75294
33608 8771
72168 20310
7196 33608
65081 28063
85113 34018
9610 20310
22459 89313
27763 28063
77561 ...

output:

0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
...

result:

ok 100000 lines

Test #15:

score: 5.88235
Accepted
time: 48ms
memory: 31284kb

input:

100000 100000
56586 89611
16689 56586
71718 56586
9941 56586
80894 56586
52129 89611
67867 9941
54715 80894
25995 52129
68623 16689
92646 54715
79986 25995
23656 92646
7824 89611
80234 54715
47682 80234
17907 23656
80529 9941
86098 54715
89002 16689
33429 80234
6620 54715
76979 17907
8581 23656
8996...

output:

0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #16:

score: 5.88235
Accepted
time: 47ms
memory: 30856kb

input:

100000 100000
45078 67876
8492 45078
54636 45078
34684 8492
21599 67876
25098 54636
25234 8492
26310 21599
77208 54636
24375 54636
97654 34684
7587 25234
16083 25234
86629 54636
3424 77208
83221 86629
23496 24375
79233 25098
92954 24375
14140 23496
80922 3424
59107 23496
91826 25098
3305 97654
10060...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines

Test #17:

score: 5.88235
Accepted
time: 69ms
memory: 36464kb

input:

100000 100000
97800 20215
43329 97800
20609 43329
63120 20609
50599 63120
37636 50599
73068 37636
46150 73068
66898 46150
82707 66898
24116 82707
1624 24116
84438 1624
74832 84438
49153 74832
60928 49153
23822 60928
98266 23822
40345 98266
93499 40345
77746 93499
94388 77746
9200 94388
91780 9200
53...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 lines