QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#748472#5020. 举办乘凉州喵,举办乘凉州谢谢喵lizhous27 258ms69916kbC++147.2kb2024-11-14 20:29:162024-11-14 20:29:16

Judging History

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

  • [2024-11-14 20:29:16]
  • 评测
  • 测评结果:27
  • 用时:258ms
  • 内存:69916kb
  • [2024-11-14 20:29:16]
  • 提交

answer

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include<set>
#include<queue>
#define mod 998244353
using namespace std;
vector <int> g[200001];
int n,q;
namespace lca
{
	int father[200001][18],deep[200001];
	void getfather(int u,int fa)
	{
		father[u][0]=fa;
		for(int i=1;i<=17;i++)
		{
			father[u][i]=father[father[u][i-1]][i-1];
		}
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(v==fa) continue;
			getfather(v,u);
		}
	}
	void getdeep(int u,int fa)
	{
		deep[u]=deep[fa]+1;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(v==fa) continue;
			getdeep(v,u);
		}
	}
	int getlca(int u,int v)
	{
		if(deep[u]>deep[v]) swap(u,v);
	    int mul=deep[v]-deep[u],w=0;
	    while(mul)
	    {
	        if(mul&1) v=father[v][w];
	        mul>>=1;
	        w++;
	    }
	    if(u==v) return u;
	    for(int i=17;i>=0;i--)
	    {
	        if(father[u][i]!=father[v][i])
	        {
	            u=father[u][i];
	            v=father[v][i];
	        }
	    }
	    return father[u][0];
	}
}
int ans[200001];
struct qry
{
	int d,id,xs;
};
namespace dfz
{
	vector <qry> Q[200001];
	int anss,mid,masiz[200001],ton[200001],szz;
	bool vis[200001];
	void add(int x,int v)
	{
		x++;
		while(x<=szz+1)
		{
//			cout<<x<<"+\n";
			ton[x]+=v;
			x+=(x&(-x));
		}
	}
	int get(int x,int ret=0)
	{
		x++;
		x=min(x,szz+1);
		while(x)
		{
//			cout<<x<<"G\n";
			ret+=ton[x];
			x-=(x&(-x));
		}
		return ret;
	}
	void getmid(int u,int fa,int sz)
	{
	    int ma=0;
	    for(int i=0;i<g[u].size();i++)
	    {
	        if(g[u][i]==fa||vis[g[u][i]]) continue;
	        getmid(g[u][i],u,sz);
	        masiz[u]+=masiz[g[u][i]]+1;
	        ma=max(ma,masiz[g[u][i]]);
	    }
	    ma=max(ma+1,sz-masiz[u]-1);
	    if(ma<anss)
	    {
	        anss=ma;
	        mid=u;
	    }
	}
	int getsiz(int u,int fa)
	{
		int ret=1;
		masiz[u]=0;
		for(int i=0;i<g[u].size();i++)
		{
			if(g[u][i]==fa||vis[g[u][i]]) continue;
			ret+=getsiz(g[u][i],u);
		}
		return ret;
	}
	void dfs(int u,int fa,int dis,int vsl)
	{
		add(dis,vsl);
		for(int v:g[u])
		{
			if(v==fa||vis[v]) continue;
			dfs(v,u,dis+1,vsl);
		}
	}
	void go(int u,int fa,int dis)
	{
		for(qry now:Q[u])
		{
			if(now.d>=dis)
			{
				////cerr<<now.id<<' '<<get(now.d-dis)<<'\n';
				ans[now.id]+=get(now.d-dis);
			}
		}
		for(int v:g[u])
		{
			if(v==fa||vis[v]) continue;
			go(v,u,dis+1);
		}
	}
	void work(int u)
	{
		//cerr<<">>"<<u<<" : \n";
		dfs(u,-1,0,1);
		for(int v:g[u])
		{
			if(vis[v]) continue;
			dfs(v,u,1,-1);
			go(v,u,1);
			dfs(v,u,1,1);
		}
		for(qry now:Q[u])
		{
			//cerr<<now.id<<' '<<get(now.d)<<' '<<szz<<'\n';
			ans[now.id]+=get(now.d);
		}
	}
	void dfz(int u)
	{
//		cout<<u<<" midis ";
		anss=10000000000;
		mid=0;
		szz=getsiz(u,-1);
		getmid(u,-1,szz);
		u=mid;
//		cout<<u<<'\n';
//		if(g[u].size()==1)
//		{
//			for(qry now:Q[u])
//			{
//				ans[now.id]++;
//			}
//			return;
//		}
		work(u);
		for(int i=0;i<=szz+1;i++) ton[i]=0;
		vis[u]=true;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(vis[v]) continue;
			dfz(v);
		}
	}
}
namespace sp
{
	int fat[200001],siz[200001],dep[200001],hson[200001],top[200001],cnt,dfn[200001],dis[200001];
	int rt[200001],LEN;
	struct T
	{
		int l,r,sum;
	}tr[2000001];
	void add(int &o,int l,int r,int x,int v)
	{
		if(!o) o=++LEN;
		if(l==r)
		{
			tr[o].sum+=v;
			return;
		}
		int mid=l+r>>1;
		if(x<=mid) add(tr[o].l,l,mid,x,v);
		else add(tr[o].r,mid+1,r,x,v);
		tr[o].sum=tr[tr[o].l].sum+tr[tr[o].r].sum;
//		cout<<o<<" "<<l<<' '<<r<<" : "<<tr[o].sum<<'\n';
	}
	int get(int o,int l,int r,int x,int y)
	{
		if(y<l||x>r||!o) return 0;
		if(x<=l&&r<=y)
		{
			return tr[o].sum;
		}
		int mid=l+r>>1;
		return get(tr[o].l,l,mid,x,y)+get(tr[o].r,mid+1,r,x,y);
	}
	void merg(int &o,int &p)
	{
		if(!p) return;
		if(!o)
		{
			o=p;
			return;
		}
		merg(tr[o].l,tr[p].l);
		merg(tr[o].r,tr[p].r);
		tr[o].sum+=tr[p].sum;
	}
	void getdfsh(int u,int fa)
	{
		fat[u]=fa;
		dep[u]=dep[fa]+1;
		int lll=0;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(v==fa) continue;
			getdfsh(v,u);
			if(siz[v]>lll)
			{
				hson[u]=v;
				lll=siz[v];
			}
			siz[u]+=siz[v];
		}
		siz[u]++;
	}
	void gettd(int u,int fa)
	{
		dfn[u] = ++cnt;
		dis[u] = cnt;
		if(hson[fat[u]]==u)
		{
			top[u]=top[fa];
		}
		else
		{
			top[u]=u;
		}
		//cerr<<u<<" : "<<top[u]<<'\n';
		if(hson[u]!=0) gettd(hson[u],u);
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(v==fa||v==hson[u]) continue;
			gettd(v,u);
		}
	}
	vector <qry> Qg[200001],Qh[200001];
	void up(int u,int d,int id,int xs)
	{
		ans[id]+=dep[u]*xs;
		Qg[u].push_back((qry){d,id,xs});
//		//cerr<<u<<" : hson "<<hson[u]<<'\n';
		Qh[hson[u]].push_back((qry){d-1,id,xs});
		int now=top[u];
		while(now!=1)
		{
//			//cerr<<now<<"\n";
			Qh[now].push_back((qry){d-1,id,-xs});
			Qh[hson[fat[now]]].push_back((qry){d-1,id,xs});
			now=top[fat[now]];
		}
	}
	int ton[200001];
	void add(int x,int v)
	{
//		//cerr<<"ADD "<<x<<'\n';
		while(x<=n)
		{
			ton[x]+=v;
			x+=(x&(-x));
		}
	}
	int get(int x,int ret=0)
	{
//		//cerr<<"GET "<<x<<'\n';
		while(x)
		{
			ret+=ton[x];
			x-=(x&(-x));
		}
		return ret;
	}
	void inton(int u,int fa,int dis,int vsl)
	{
		add(dis,vsl);
		for(int v:g[u])
		{
			if(v==fa) continue;
			inton(v,u,dis+1,vsl);
		}
	}
	void workg(int u,int fa)
	{
		for(int v:g[u])
		{
			if(v==fa) continue;
			if(v!=hson[u])
			{
				inton(v,u,1,1);
			}
		}
		for(qry now:Qg[u])
		{
			ans[now.id]+=now.xs*get(now.d);
		}
		for(int v:g[u])
		{
			if(v==fa) continue;
			workg(v,u);
		}
		for(int v:g[u])
		{
			if(v==fa) continue;
			if(v!=hson[u])
			{
				inton(v,u,1,-1);
			}
		}
	}
	void workh(int u,int fa)
	{
		for(int v:g[u])
		{
			if(v==fa) continue;
			workh(v,u);
			merg(rt[u],rt[v]);
		}
		add(rt[u],1,n,dep[u],1);
		for(qry now:Qh[u])
		{
			if(now.d<0) continue;
			//cerr<<u<<" "<<now.d<<" : "<<get(rt[u],1,n,dep[u],dep[u]+now.d)<<" to "<<now.id<<" times "<<now.xs<<'\n';
			ans[now.id]+=now.xs*get(rt[u],1,n,dep[u],dep[u]+now.d);
		}
	}
}
signed main()
{
//	freopen("tiv.in","r",stdin);
//	freopen("tiv.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1,u,v;i<n;i++)
	{
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	lca::getfather(1,0);
	lca::getdeep(1,0);
	sp::getdfsh(1,0);
	sp::gettd(1,0);
	cin>>q;
	for(int i=1,u,v,d;i<=q;i++)
	{
		cin>>u>>v>>d;
		//cerr<<u<<' '<<v<<' '<<d<<"\n";
		int lca=lca::getlca(u,v);
//		//cerr<<lca<<" ";
		dfz::Q[lca].push_back((qry){d,i,1});
		sp::up(u,d,i,1);
		sp::up(v,d,i,1);
		sp::up(lca,d,i,-2);
	}
	//cerr<<"SSSS\n";
	for(int i=1;i<=q;i++)
	{
		//cerr<<ans[i]<<'\n';
	}
	dfz::dfz(1);
	//cerr<<"DFZ\n";
	for(int i=1;i<=q;i++)
	{
		//cerr<<ans[i]<<'\n';
	}
	sp::workg(1,0);
	//cerr<<"WORKG\n";
	for(int i=1;i<=q;i++)
	{
		//cerr<<ans[i]<<'\n';
	}
	sp::workh(1,0);
	//cerr<<"WORKH\n";
	for(int i=1;i<=q;i++)
	{
		cout<<ans[i]<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 10ms
memory: 38536kb

input:

4988
1 2
1 3
1 4
4 5
1 6
3 7
3 8
5 9
4 10
6 11
3 12
9 13
11 14
8 15
11 16
1 17
7 18
8 19
18 20
7 21
10 22
15 23
18 24
4 25
24 26
9 27
23 28
3 29
3 30
30 31
11 32
18 33
2 34
32 35
29 36
29 37
19 38
9 39
6 40
25 41
16 42
31 43
6 44
42 45
32 46
27 47
32 48
44 49
7 50
10 51
24 52
46 53
30 54
46 55
39 56...

output:

3226
2028
4988
208
252
3970
3886
2013
4974
2118
308
391
4768
312
4954
4988
4974
1551
4981
12
1856
4825
4974
4974
19
82
4960
4680
208
4870
474
3693
808
1880
213
3394
1203
266
84
4822
3334
70
81
4501
4960
668
4866
4974
113
490
75
163
209
2159
4981
4143
100
3168
232
66
4864
525
4958
390
4713
2305
15
49...

result:

ok 4966 numbers

Test #2:

score: 7
Accepted
time: 13ms
memory: 39064kb

input:

4914
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27 ...

output:

3378
4914
231
4914
4914
3378
22
4914
4914
2559
4914
75
219
1407
1138
863
24
3890
4914
4914
399
399
13
139
77
4914
4095
3071
4914
23
151
110
1407
43
54
4914
4914
1919
2559
77
735
3071
24
133
479
4914
33
831
4
4914
4914
79
4914
199
3890
3071
73
567
15
75
21
126
4914
4914
203
4914
75
127
62
41
4914
409...

result:

ok 4975 numbers

Test #3:

score: 7
Accepted
time: 13ms
memory: 38220kb

input:

4921
1151 2767
2767 322
322 4451
4451 4867
4867 1265
1265 3197
3197 3890
3890 1052
1052 1407
1407 1578
1578 566
566 2965
2965 260
260 4908
4908 308
308 553
553 2845
2845 4249
4249 1284
1284 73
73 1088
1088 277
277 1878
1878 4128
4128 3609
3609 2126
2126 149
149 3467
3467 1653
1653 4913
4913 3604
360...

output:

4921
3192
3260
3983
949
2080
605
3471
4901
2020
2552
1570
3325
3643
458
1296
3072
3423
3045
2569
1720
3195
1908
4397
1536
2799
3072
2443
3176
3311
1403
1119
842
3028
2387
1903
2303
4921
2149
1974
4153
2053
2888
2344
3264
3709
3443
3601
2571
1207
4519
3745
959
1920
1305
1706
1743
522
1266
2153
1812
1...

result:

ok 4930 numbers

Test #4:

score: 7
Accepted
time: 20ms
memory: 35904kb

input:

4942
877 4180
4180 4409
4409 2233
2233 3491
3491 3459
3459 4501
4501 2192
2192 3539
3539 4379
4379 4346
4346 1553
1553 2100
2100 3426
3426 3461
3461 811
811 2981
2981 1493
1493 610
610 599
599 1741
1741 3216
3216 1646
1646 1016
1016 3757
3757 2570
2570 2900
2900 4649
4649 1014
1014 538
538 4288
4288...

output:

4236
3338
4942
4942
4942
4942
1551
1272
3885
4140
4942
3627
3132
3991
3157
4024
4942
4942
3761
3064
238
4942
4942
4942
4942
4942
2256
4942
649
4496
4942
4942
4491
866
4208
4942
4942
4726
4942
4462
4942
4942
4234
2676
2593
4942
4088
4942
2704
3344
3560
4942
4942
4461
4511
4634
3437
2884
3842
4942
494...

result:

ok 4910 numbers

Test #5:

score: 7
Accepted
time: 16ms
memory: 31996kb

input:

4996
1 2
2 3
1 4
4 5
4 6
3 7
4 8
8 9
3 10
9 11
5 12
7 13
12 14
8 15
8 16
14 17
10 18
15 19
17 20
15 21
19 22
21 23
14 24
20 25
25 26
21 27
20 28
19 29
29 30
24 31
31 32
29 33
27 34
34 35
31 36
27 37
30 38
35 39
38 40
37 41
34 42
41 43
43 44
42 45
36 46
37 47
47 48
47 49
41 50
50 51
46 52
50 53
51 54...

output:

4869
3419
3000
4640
4996
4996
3854
4165
4542
4996
1758
3584
3011
4996
4996
4383
2064
4199
2786
2470
4759
4996
4657
4157
2443
2594
1823
3215
1635
3908
1903
3207
2153
4448
4996
4996
3071
2649
3452
4996
1235
1599
2732
2244
2311
4618
1250
4577
3498
4941
1058
3498
3539
3415
907
4170
4996
4144
2235
2664
4...

result:

ok 4952 numbers

Test #6:

score: 7
Accepted
time: 14ms
memory: 31896kb

input:

4935
1 2
1 3
4 2
5 2
6 4
7 4
8 6
9 6
10 8
11 8
12 10
13 10
14 12
15 12
16 14
17 14
18 16
19 16
20 18
21 18
22 20
23 20
24 22
25 22
26 24
27 24
28 26
29 26
30 28
31 28
32 30
33 30
34 32
35 32
36 34
37 34
38 36
39 36
40 38
41 38
42 40
43 40
44 42
45 42
46 44
47 44
48 46
49 46
50 48
51 48
52 50
53 50
5...

output:

4442
4133
346
3268
4850
3512
3312
3581
4092
4655
2256
3950
3157
3480
4935
4188
4935
1593
1135
4935
4935
4875
4108
3771
4158
4935
4935
3156
3148
1814
4935
3368
4303
2861
4917
2370
3992
4764
2772
4935
4935
2640
4935
4691
2291
4268
1798
4530
3058
3219
4935
3141
4935
2699
4547
2164
2495
3049
370
3409
21...

result:

ok 4992 numbers

Test #7:

score: 7
Accepted
time: 8ms
memory: 31620kb

input:

4919
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

2653
3219
4302
1418
1713
713
3341
647
487
1508
971
4851
4443
3078
2380
2267
4171
18
2056
1833
3136
817
4375
4103
3423
433
3967
725
282
2358
4171
1680
3350
2403
802
1855
137
2091
3731
1061
581
1273
4783
133
1911
4239
4233
678
3127
3481
284
1896
435
593
4781
103
4647
1615
1231
2689
574
1833
4783
645
4...

result:

ok 4980 numbers

Test #8:

score: 7
Accepted
time: 18ms
memory: 34200kb

input:

4973
1 4517
2 744
3 1115
4 3191
5 4186
6 4608
7 3898
8 3939
9 1998
10 2287
11 2277
12 4200
13 4935
14 3955
15 3683
16 278
17 547
18 3351
19 2642
20 4050
21 3457
22 2337
23 3435
24 1476
25 4853
26 3985
27 736
28 3016
29 4840
30 3866
31 4567
32 4067
33 3724
34 1872
35 1533
36 4787
37 53
38 1632
39 295...

output:

91
2487
2646
1791
2447
3327
532
1801
1079
1526
1236
77
4028
3401
4103
1573
3540
1641
452
52
2497
3128
2593
734
1293
3213
1786
1626
2130
2033
1935
2673
1758
1838
1284
758
2952
301
947
2875
3073
1462
2615
2842
3561
1969
1416
3088
2476
1082
696
3665
2041
3263
3063
2988
1402
1050
2967
3696
2309
3767
281...

result:

ok 4982 numbers

Subtask #2:

score: 0
Memory Limit Exceeded

Test #9:

score: 0
Memory Limit Exceeded

input:

199995
1 2
2 3
2 4
1 5
3 6
5 7
6 8
4 9
2 10
5 11
5 12
1 13
1 14
1 15
13 16
1 17
10 18
16 19
11 20
8 21
17 22
4 23
19 24
7 25
22 26
8 27
14 28
1 29
9 30
3 31
3 32
21 33
19 34
26 35
34 36
5 37
29 38
22 39
5 40
13 41
28 42
8 43
35 44
22 45
14 46
12 47
32 48
11 49
8 50
18 51
23 52
18 53
4 54
6 55
10 56
...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Memory Limit Exceeded

Test #25:

score: 0
Memory Limit Exceeded

input:

199991
1 2
2 3
3 4
3 5
5 6
3 7
1 8
8 9
8 10
10 11
1 12
1 13
13 14
4 15
12 16
13 17
17 18
8 19
3 20
9 21
16 22
10 23
1 24
7 25
6 26
12 27
4 28
21 29
27 30
30 31
21 32
19 33
20 34
17 35
7 36
13 37
24 38
37 39
30 40
31 41
15 42
9 43
32 44
41 45
18 46
38 47
8 48
35 49
13 50
35 51
47 52
35 53
48 54
44 55...

output:


result:


Subtask #5:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #33:

score: 20
Accepted
time: 194ms
memory: 62684kb

input:

49994
1 2
1 3
1 4
4 5
4 6
2 7
5 8
2 9
5 10
3 11
11 12
5 13
2 14
5 15
14 16
15 17
15 18
11 19
7 20
2 21
1 22
21 23
15 24
22 25
16 26
22 27
16 28
11 29
17 30
21 31
3 32
22 33
3 34
33 35
34 36
17 37
22 38
21 39
22 40
11 41
14 42
30 43
42 44
27 45
41 46
21 47
5 48
17 49
40 50
31 51
23 52
40 53
17 54
39 ...

output:

49991
27842
12698
41582
41674
49129
139
49931
49986
49966
33701
41907
520
7
49823
37296
45378
43279
22
45415
43709
139
1658
12239
1106
48337
42014
49964
1603
49935
1295
38134
484
49771
13800
36652
12183
1503
49825
148
49211
195
46766
38915
49990
26440
26888
1176
140
37080
8196
5750
49964
49612
49935...

result:

ok 49997 numbers

Test #34:

score: 20
Accepted
time: 213ms
memory: 69916kb

input:

49994
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31
16 32
16 33
17 34
17 35
18 36
18 37
19 38
19 39
20 40
20 41
21 42
21 43
22 44
22 45
23 46
23 47
24 48
24 49
25 50
25 51
26 52
26 53
27 54
27...

output:

13823
49994
49994
24
367
48
19455
367
2175
6655
1215
3839
17407
9727
49994
28671
49994
3039
49994
49151
1071
3839
3839
49994
1215
49994
671
3839
49994
591
3711
49994
15359
49994
28
2175
367
28671
10751
49994
11263
98
107
41802
4543
199
36863
49994
49994
1183
367
49151
40959
1071
2111
6655
11263
1927...

result:

ok 49997 numbers

Test #35:

score: 20
Accepted
time: 194ms
memory: 52456kb

input:

49992
18276 49801
49801 29872
29872 18038
18038 5160
5160 47615
47615 9368
9368 48020
48020 18919
18919 22293
22293 28784
28784 26366
26366 16335
16335 996
996 28965
28965 7132
7132 9570
9570 22976
22976 16634
16634 22619
22619 28051
28051 11004
11004 1360
1360 41340
41340 43214
43214 24436
24436 46...

output:

46017
14490
35283
47122
47076
47522
33249
14538
36480
29309
30496
22079
35856
47676
19688
29847
49992
46968
30446
36597
41074
24827
42181
37491
49992
33422
23462
34849
43986
32605
22539
43614
40945
48216
9983
37908
40591
47737
22962
33035
23333
35206
19572
33241
18254
44132
21667
21688
43981
44138
3...

result:

ok 49996 numbers

Test #36:

score: 20
Accepted
time: 171ms
memory: 48108kb

input:

49991
36788 8430
8430 29122
29122 7462
7462 34863
34863 38520
38520 38159
38159 10299
10299 26846
26846 40569
40569 35453
35453 39237
39237 37963
37963 2323
2323 5574
5574 49072
49072 8151
8151 9543
9543 14269
14269 15375
15375 38098
38098 46141
46141 29199
29199 13837
13837 3056
3056 13396
13396 20...

output:

10717
26965
17476
49991
49991
12680
32753
49991
44617
49991
49991
49991
49991
29760
49991
49991
49991
49991
49991
49991
15545
49991
19088
21948
23809
49991
46952
49991
49991
49991
36059
37144
49991
49991
41837
49991
49991
49991
49991
49991
49991
49991
49991
49991
49991
49991
28977
43912
49991
49991
...

result:

ok 49999 numbers

Test #37:

score: 20
Accepted
time: 176ms
memory: 54988kb

input:

49992
1 2
1 3
3 4
4 5
5 6
6 7
6 8
3 9
9 10
4 11
7 12
6 13
7 14
9 15
10 16
8 17
13 18
18 19
15 20
17 21
19 22
13 23
23 24
21 25
19 26
19 27
23 28
19 29
25 30
27 31
28 32
25 33
30 34
34 35
28 36
32 37
35 38
36 39
34 40
39 41
41 42
39 43
34 44
41 45
36 46
44 47
39 48
48 49
44 50
43 51
44 52
49 53
53 54...

output:

49992
44208
40560
49983
44985
19872
12959
21712
45703
31309
33201
49992
21924
36480
16502
31883
16181
36221
24725
42191
49992
35236
49992
35558
23642
20260
20165
11056
7575
49992
47236
49992
49992
43883
49992
35916
44169
49992
32253
41307
11731
4410
36173
36842
41712
18415
15542
34255
14712
35964
31...

result:

ok 49997 numbers

Test #38:

score: 20
Accepted
time: 149ms
memory: 54060kb

input:

49992
1 2
1 3
4 2
5 2
6 4
7 4
8 6
9 6
10 8
11 8
12 10
13 10
14 12
15 12
16 14
17 14
18 16
19 16
20 18
21 18
22 20
23 20
24 22
25 22
26 24
27 24
28 26
29 26
30 28
31 28
32 30
33 30
34 32
35 32
36 34
37 34
38 36
39 36
40 38
41 38
42 40
43 40
44 42
45 42
46 44
47 44
48 46
49 46
50 48
51 48
52 50
53 50
...

output:

39583
37249
43384
29100
15677
17788
5806
32912
32417
42927
35958
35935
20363
17412
28393
13083
49992
17231
44476
34557
26645
31001
33105
49992
42169
38467
49992
34467
22711
30648
32377
40585
16552
48257
37613
16909
35471
49992
25468
18922
26730
24191
41997
49299
41755
17953
37963
49992
2358
9448
499...

result:

ok 49991 numbers

Test #39:

score: 20
Accepted
time: 127ms
memory: 50572kb

input:

49992
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53...

output:

2119
8453
47550
40224
8275
48438
21511
29343
11178
12840
37338
17769
49992
40224
26178
11775
11405
48882
23283
9518
26016
49548
36450
8684
22461
35730
41556
10352
38656
26589
8503
36628
20425
46879
43554
47994
15804
12373
28369
21219
43776
38004
38886
35562
20679
5674
16613
25704
29120
2178
21055
31...

result:

ok 49990 numbers

Test #40:

score: 20
Accepted
time: 258ms
memory: 56816kb

input:

49996
1 34528
2 1933
3 8542
4 37866
5 13181
6 33418
7 31611
8 9600
9 47851
10 22729
11 34920
12 20679
13 13874
14 35815
15 1308
16 40327
17 20697
18 34642
19 45144
20 40726
21 36899
22 49440
23 42507
24 34983
25 34496
26 41651
27 19121
28 30392
29 48080
30 18302
31 28030
32 22472
33 26275
34 17680
3...

output:

177
25075
32138
400
36791
38592
28612
12464
10352
43337
36452
43158
13659
5593
29988
23224
7087
23922
25697
21833
5923
44766
33658
16893
26217
30297
37628
43546
12097
2042
26157
34289
36173
22194
3792
36001
44332
6645
23987
19246
32699
8178
25580
8650
32659
39845
21279
24361
32241
26532
20586
3931
3...

result:

ok 49996 numbers

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%