QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#501049	#9159. 登山	tanxi^#	25	671ms	63460kb	C++14	4.5kb	2024-08-02 11:48:24	2024-08-02 11:48:25

Judging History

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

[2024-08-02 11:48:25]
评测

测评结果：25
用时：671ms
内存：63460kb

查看

[2024-08-02 11:48:24]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9,mod=998244353;
int dep[N],f[N],g[N],L[N],R[N],fa[N],d[N];
int dfn[N],siz[N],cnt,mp[N],mx[N],son[N];
struct xdt
{
	int val[N<<2],sum[N<<2],lz[N<<2];
	void pushup(int p)
	{
		val[p]=(val[p<<1]+val[p<<1|1])%mod;
		sum[p]=(sum[p<<1]+sum[p<<1|1])%mod;
	}
	void pushdown(int p)
	{
		if(!lz[p])
		return;
		sum[p<<1]=(sum[p<<1]+lz[p]*val[p<<1]%mod+mod)%mod;
		sum[p<<1|1]=(sum[p<<1|1]+lz[p]*(val[p<<1|1])%mod+mod)%mod;
		lz[p<<1]+=lz[p];
		lz[p<<1|1]+=lz[p];
		lz[p]=0;
	}
	void update(int p,int l,int r,int x,int k)
	{
		if(l==r)
		{
			val[p]=k;sum[p]=0;
			return;
		}
		pushdown(p);
		int mid=(l+r)/2;
		if(x<=mid)
		update(p<<1,l,mid,x,k);
		else
		update(p<<1|1,mid+1,r,x,k);
		pushup(p);
	}
	void add(int p,int l,int r,int L,int R,int k)
	{
		if(L>R)
		return;
		if(L<=l&&r<=R)
		{
			sum[p]=(sum[p]+val[p]*k%mod+mod)%mod;
			lz[p]+=k;
			return;
		}
		pushdown(p);
		int mid=(l+r)/2;
		if(L<=mid)
		add(p<<1,l,mid,L,R,k);
		if(R>mid)
		add(p<<1|1,mid+1,r,L,R,k);
		pushup(p);
	}
	int query(int p,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R)
		{
			return sum[p];
		}
		int mid=(l+r)/2;
		pushdown(p);
		int now=0;
		if(L<=mid)
		now=(now+query(p<<1,l,mid,L,R))%mod;
		if(R>mid)
		now=(now+query(p<<1|1,mid+1,r,L,R))%mod;
		return now;
	}
}T;
int tr[N],ls[N],rs[N],dist[N];
int sz[N];
priority_queue<pair<int,int> >root;
void pushup(int p)
{
	dist[p]=dist[rs[p]]+1;
	sz[p]=sz[ls[p]]+sz[rs[p]]+1;
}
int merge(int x,int y)
{
	if(!x||!y)
	return x+y;
	if(tr[x]<tr[y])
	swap(x,y);
	rs[x]=merge(rs[x],y);
	if(dist[ls[x]]<dist[rs[x]])
	swap(ls[x],rs[x]);
	return x;
}
int del(int x)
{
	int p=merge(ls[x],rs[x]);
	ls[x]=rs[x]=tr[x]=dist[x]=0;
	return p;
}
int id,n,fl;
struct bian
{
	int to,lt;
}b[N<<1];
int head[N],top;
void mkb(int l,int r)
{
	b[++top]={r,head[l]};
	head[l]=top;
}
void dfs(int x)
{
	siz[x]=1;
	dfn[x]=++cnt;
	mp[cnt]=x;
	son[x]=0;
	for(int t=head[x];t;t=b[t].lt)
	{
		int y=b[t].to;
		dfs(y);
		siz[x]+=siz[y];
		if(siz[y]>siz[son[x]])
		son[x]=y;
	}
}
struct Cao
{
	int opt,l,r,k;
}stk[N*30];
int tp;
void dsu(int x,bool flag)
{
	for(int t=head[x];t;t=b[t].lt)
	{
		int y=b[t].to;
		if(y==son[x])
		continue;
		dsu(y,false);
	}
	if(son[x])
	{
		dsu(son[x],true);
	}
	int rt=x,rd=d[x];
	ls[x]=rs[x]=0;
	tr[x]=L[x];
	sz[x]=1;
	vector<int>nd;
	nd.clear();
	while(!root.empty()&&root.top().first>rd)
	{
		int p=root.top().second;
		while(tr[p]>rd)
		{
			stk[++tp]={1,tr[p],root.top().first,1};
			p=del(p);
		}
		stk[++tp]={1,rd+1,root.top().first,sz[p]};
		if(p)
		{
			nd.push_back(p);
		}
		root.pop();
	}
	int p=0;
	for(auto u:nd)
	{
		p=merge(p,u);
	}
	if(p)
	root.push({rd,p});
	if(min(rd,R[x])>=L[x])
	{
		stk[++tp]={1,L[x],min(rd,R[x]),-1};
		root.push({min(rd,R[x]),x});
	}
	mx[x]=d[x];
	for(int t=head[x];t;t=b[t].lt)
	{
		int y=b[t].to;
		if(y==son[x])
		continue;
		for(int i=dfn[y];i<dfn[y]+siz[y];i++)
		{
			mx[mp[i]]=min(mx[fa[mp[i]]],d[mp[i]]);
			if(L[mp[i]]<=min(mx[mp[i]],R[mp[i]]))
			{
				tr[mp[i]]=L[mp[i]];
				ls[mp[i]]=rs[mp[i]]=0;
				sz[mp[i]]=1;
				stk[++tp]={1,L[mp[i]],min(mx[mp[i]],R[mp[i]]),-1};
				root.push({min(mx[mp[i]],R[mp[i]]),mp[i]});
			}
		}
	}
	stk[++tp]={3,dep[x],dep[x],x};
	stk[++tp]={2,1,n,x};
	if(!flag)
	{
		while(!root.empty())
		{
			int p=root.top().second;
			int t=root.top().first;
			while(p)
			{
				stk[++tp]={1,tr[p],t,1};
				p=del(p);
			}
			root.pop();
		}
	}
}
int td;
signed main()
{
	// freopen("ex_5.in","r",stdin);
	// freopen("mountain.out","w",stdout);
	cin>>id>>td;
	while(td--)
	{
		cnt=0;
		memset(head,0,sizeof(head));
		top=0;
		cin>>n;
		memset(f,0,sizeof(f));
		dep[1]=0;
		for(int i=2;i<=n;i++)
		{
			cin>>fa[i];
			mkb(fa[i],i);
			dep[i]=dep[fa[i]]+1;
			int l,r;
			cin>>l>>r;
			L[i]=dep[i]-r;
			R[i]=dep[i]-l;
			cin>>d[i];
			d[i]=dep[i]-d[i]-1;
			L[i]++;
			R[i]++;
			d[i]++;
		}
		L[1]=114514;
		R[1]=0;
		for(int i=1;i<=n;i++)
		dep[i]++;
		dfs(1);
		dsu(1,false);
		f[1]=1;
		while(tp)
		{
 			if(stk[tp].opt==1)
			{
				T.add(1,1,n,stk[tp].l,stk[tp].r,stk[tp].k);
			}
			if(stk[tp].opt==2)
			{
				f[stk[tp].k]=T.query(1,1,n,1,n);
			}
			if(stk[tp].opt==3)
			{
				T.update(1,1,n,stk[tp].l,f[stk[tp].k]);
			}
			f[1]=1;
			tp--;
		}
		for(int i=2;i<=n;i++)
		cout<<f[i]<<' ';
		cout<<'\n';
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 5

Accepted

time: 3ms

memory: 19920kb

input:

output:

result:

ok 20 numbers

Pretest #2:

score: 0

Wrong Answer

time: 2ms

memory: 22124kb

input:

output:

19 18 35 998238226 998237948 15 998236270 998236355 998237910 15 311 223 998237910 451 998231905 998229214 998236328 416 998236220 998228098 998236323 558 319 998236220 998217638 998216292 304 451 998217712 998216267 5280 2615 998217677 1641 998213843 1573 998217575 91 998213752 3135 998209568 99821...

result:

wrong answer 4th numbers differ - expected: '1', found: '998238226'

Pretest #3:

score: 0

Wrong Answer

time: 0ms

memory: 22424kb

input:

output:

20 18 997420258 997422893 173 997422075 997421122 152 169 997422036 130 3452 997422051 997406410 2745 997395963 996600262 997384522 2727 3422 997360568 2091 1748 997266778 14224 997286843 997290111 14186 1709 997252400 997259235 997259235 1709 94813 37322 997147957 997061101 16277 997296994 1840 996...

result:

wrong answer 3rd numbers differ - expected: '40', found: '997420258'

Pretest #4:

score: 0

Wrong Answer

time: 87ms

memory: 25700kb

input:

output:

584180864 584181200 28 83 25 584180442 108 584178904 584177293 79 21 584176788 584177321 21 584173729 133 533 584094788 1227 584173941 584109331 1112 584077389 584142481 423 584088143 236 20 3562 328 583946799 583998095 1518 584077037 584027782 831 584054842 584080568 615 615 16044 581089264 23708 5...

result:

wrong answer 1st numbers differ - expected: '1', found: '584180864'

Pretest #5:

score: 0

Wrong Answer

time: 79ms

memory: 27752kb

input:

output:

56654778 35 56655710 113310045 34 169967129 34 113311419 56639990 207 444 56642647 56648418 374 56634696 56640265 64 56635445 56636434 64 56636159 56632501 64 56635722 998244347 56639955 169911834 92 56634579 56639955 998244312 56517567 1205 56576625 1135 56634510 56576625 1099 56365645 56452634 162...

result:

wrong answer 1st numbers differ - expected: '2', found: '56654778'

Pretest #6:

score: 5

Accepted

time: 559ms

memory: 62580kb

input:

6
4
100000
1 1 1 0
2 1 1 0
3 1 1 0
4 2 2 0
5 1 1 0
6 2 2 0
7 6 6 0
8 3 3 0
9 6 6 0
10 8 8 0
11 6 6 0
12 12 12 0
13 11 11 0
14 2 2 0
15 2 2 0
16 2 2 0
17 9 9 0
18 1 1 0
19 4 4 0
20 18 18 0
21 13 13 0
22 20 20 0
23 3 3 0
24 21 21 0
25 8 8 0
26 11 11 0
27 11 11 0
28 3 3 0
29 21 21 0
30 1 1 0
31 27 27 0...

output:

7 90 1343 13340 200010 2186770 17480820 279693113 800242414 420706509 214087588 358274752 946289212 530647994 955227776 663050301 438245147 621009062 780623708 80919478 728275212 743623748 978006196 735181462 256088384 612217572 335562169 696082683 110948988 53450390 637356472 107616671 988788196 54...

result:

ok 399996 numbers

Pretest #7:

score: 5

Accepted

time: 649ms

memory: 58964kb

input:

output:

1 1 1 1 31 2 2 94 31 1298 33 1 126 41443 62 95 35 93 1490650 94 49108564 2 41443 62 31502098 1491949 41443 1 1 882058713 1298 808538694 650336433 808538694 808538695 53283330 1298 31502098 1 31502098 319947267 692436002 360370658 1534689 1298 41443 692394559 41443 518136386 1298 972986764 32 6923530...

result:

ok 399996 numbers

Pretest #8:

score: 5

Accepted

time: 533ms

memory: 63460kb

input:

8
4
100000
1 1 1 0
2 2 2 0
3 3 3 0
4 4 4 2
5 2 2 1
6 6 6 0
7 2 2 0
8 7 7 3
9 4 4 3
10 1 1 4
11 3 3 0
12 8 8 11
13 13 13 7
14 5 5 10
15 8 8 11
16 14 14 5
17 9 9 2
18 17 17 7
19 3 3 1
20 1 1 9
21 14 14 5
22 5 5 17
23 8 8 14
24 8 8 9
25 24 24 7
26 24 24 7
27 17 17 8
28 27 27 27
29 26 26 6
30 17 17 14
3...

output:

12 23 22 21 42 62 61 19 49 7 26 7 77 76 76 156 133 114 258 102 102 41 41 48 48 36 13 6 140 118 41 203 155 155 41 61 61 61 328 279 279 123 111 111 111 225 204 90 109 252 150 109 150 109 47 47 28 28 28 6 120 120 6 18 18 59 59 18 32 32 32 73 73 73 672 631 631 352 311 32 380 483 374 408 275 395 275 234 ...

result:

ok 399996 numbers

Pretest #9:

score: 5

Accepted

time: 584ms

memory: 56924kb

input:

output:

4 6 0 1 23 0 11 44 0 1 5 3 62 1 0 2 1 18 1 220 1 1 45 202 0 1 44 399 0 179 23 18 0 554 0 0 155 155 0 261 0 701 220 0 1214 971 23 417 269 155 148 0 779 0 85 40 62 756 62 554 1011 40 0 0 40 220 2426 18 0 0 0 2425 18 650 40 0 3399 502 2845 479 0 0 1631 62 0 62 18 1170 62 345 283 2428 646 1214 491 283 1...

result:

ok 399996 numbers

Pretest #10:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #11:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #12:

score: 0

Time Limit Exceeded

input:

12
4
100000
1 1 1 0
1 1 1 0
3 1 2 0
3 1 2 0
4 1 1 0
4 1 3 0
6 2 4 0
7 2 4 0
9 1 4 0
8 1 3 0
11 3 3 0
11 5 6 0
12 1 2 0
14 3 3 0
13 2 7 0
16 2 3 0
17 2 4 0
17 7 9 0
17 3 8 0
20 2 6 0
21 10 11 0
21 6 11 0
21 7 9 0
23 3 4 0
24 5 11 0
26 6 9 0
26 5 7 0
27 12 13 0
29 10 10 0
28 1 3 0
31 13 15 0
32 7 13 0...

output:

result:

Pretest #13:

score: 0

Time Limit Exceeded

input:

13
4
100000
1 1 1 0
2 1 2 0
3 2 2 2
4 2 4 1
5 1 2 4
6 4 6 2
7 1 6 4
8 6 6 5
9 5 8 8
10 6 6 1
11 8 11 5
12 8 11 1
13 4 8 6
14 4 7 1
15 11 15 5
16 1 1 10
17 6 9 7
18 8 16 2
19 2 9 10
20 6 20 7
21 12 14 11
22 9 14 14
23 6 7 22
24 12 14 11
25 20 20 21
26 10 20 0
27 19 26 8
28 21 23 12
29 4 13 23
30 15 2...

output:

28 55 26 109 25 246 162 79 24 1161 1052 1188 970 2125 699 480 1822 2880 993 4442 286 21 21 3643 242 9482 1296 566 133 133 1182 1206 15395 21157 535 535 4596 669 669 14195 426 21885 11717 16363 25769 25769 3232 53489 1535 1320 137588 110499 116023 113199 42633 42633 42143 50808 998243834 67809 7380 2...

result:

Pretest #14:

score: 0

Time Limit Exceeded

input:

14
4
100000
1 1 1 0
2 1 1 1
1 1 1 0
2 1 2 1
4 2 2 1
5 2 2 1
7 1 4 1
8 2 5 3
8 5 5 3
10 2 3 5
11 1 6 5
10 1 4 5
12 5 8 1
12 3 6 5
13 3 6 2
15 2 5 8
17 6 7 6
18 6 8 5
17 10 10 1
18 4 5 5
20 4 11 7
22 8 9 4
23 9 13 12
24 9 13 10
24 6 8 7
26 3 13 13
26 11 14 11
28 11 11 2
27 9 16 8
30 6 12 0
31 13 17 16...

output:

38 853741723 853742206 37 853742623 150 149 853740980 34 33 109 853734339 853731115 69 853735538 32 853679163 853731222 407 853702469 406 329 30 853622129 553 295 853303659 853336508 2482 1269 179 852885085 853303985 1750 853032558 853056684 2542 2542 14502 850693950 850499982 1338 1013 850158860 85...

result:

Pretest #15:

score: 0

Time Limit Exceeded

input:

output:

273289154 69 271175510 271230028 542405605 271230027 914782415 1239 542460193 271110103 283984629 813690151 368204106 1168 271175510 94914951 269461482 27048 271110103 842773490 25739 283984630 379657119 10695475 390349910 116226 10695475 10695475 663641750 10695476 915908274 75627 925477890 9230903...

result:

Pretest #16:

score: 0

Time Limit Exceeded

input:

output:

55 304983279 304988519 304988518 304988520 109 53 304984268 304988519 2115 1893 303893862 304020639 304983495 608048109 302908017 12197 608045941 609006248 12033 302574579 605551965 302905849 4708 302906119 302934470 302908017 302924535 207 302502835 302906014 302929209 302918046 302905849 43 302905...

result:

Pretest #17:

score: 0

Time Limit Exceeded

input:

output:

212947629 212948816 212948816 54 51 212946660 49 638841002 212931495 209 212944454 425894342 212944921 212907030 212944504 351 212944920 212903589 212944453 212907025 212906926 44 212944820 212856177 212906926 212944862 212903748 582 212944708 212907080 212903691 212944608 212037477 4745 212431412 2...

result:

Pretest #18:

score: 0

Time Limit Exceeded

input:

output:

60 917266808 917358639 893 917306992 832 917358578 7915 837003227 4933 917358576 917888941 916648077 1423 916538761 917023756 1423 917266806 1422 917266806 917029885 469 917151370 4041 9986 915234559 914522187 5279 916493871 831462171 346 346 916529121 916493870 916479297 85891 907545245 43597 70831...

result:

Pretest #19:

score: 0

Time Limit Exceeded

input:

output:

38 641042020 37 683 641042518 168279 641013544 924883199 792 137119446 640990494 567704290 678 22925 274352448 567895493 93543 2077 925051478 2076 522 168279 640550768 485 640582610 640991212 447 595 640643923 283328712 640990492 640678557 3290 611388381 640557645 640723979 34325 614870778 627653588...

result:

Pretest #20:

score: 0

Time Limit Exceeded

input:

output:

52 103 49 481767673 963551194 481792240 200 481828092 97 928876541 97 481823475 481830786 963659137 200 45 481830942 2993 2043 963659032 481831096 963658877 378077934 481479243 1839 480717742 481479039 481479828 481479039 4700 479660979 480707179 480704269 481479385 2040 479993892 480706470 4280 479...

result:

Final Tests

Test #1:

score: 5

Accepted

time: 0ms

memory: 22628kb

input:

output:

result:

ok 20 numbers

Test #2:

score: 0

Wrong Answer

time: 2ms

memory: 22136kb

input:

output:

34 998242666 998244016 1 236 998238313 998242361 1 998238592 998237412 28 998237106 998242633 998242598 998238488 2124 998234302 998242598 2089 998238454 998242598 998211675 998236155 998236419 7628 998237107 4976 998207780 998242632 998198607 998242868 998196219 193 998194596 998195463 998237107 99...

result:

wrong answer 2nd numbers differ - expected: '69', found: '998242666'

Test #3:

score: 0

Wrong Answer

time: 4ms

memory: 22848kb

input:

output:

25 249 447 997755096 997761868 997762116 997266638 997761843 16 997761842 997755173 1038 997761868 997730858 997746688 997755147 997733165 513 997733149 996778274 2703 997273307 2256 997266534 997703269 995806411 2256 997757351 4491 997702072 13711 997693243 997702078 1523 997688894 997708535 998243...

result:

wrong answer 4th numbers differ - expected: '129', found: '997755096'

Test #4:

score: 0

Wrong Answer

time: 83ms

memory: 21784kb

input:

output:

559141243 559142226 559143385 679185801 41 559143385 40 799228217 118 117 559131187 34 559129730 559128482 559135394 120026516 33 33 559139559 559141281 559139639 33 2118 558907210 559027743 1900 558824933 558906975 559027701 1613 558907096 557485383 3460 557688306 558907015 557687938 3420 558825087...

result:

wrong answer 1st numbers differ - expected: '3', found: '559141243'

Test #5:

score: 0

Wrong Answer

time: 81ms

memory: 24460kb

input:

output:

34 33 206529201 206532021 65 206531151 206532428 206532985 206532988 32 619597028 413065006 413065006 206515445 265 206532984 264 413038407 34418647 229 95 206507694 223 206495853 206496402 206497418 206499632 26 5427 206416338 206496314 206449822 878 206411917 206449196 206496805 206413333 24 20644...

result:

wrong answer 3rd numbers differ - expected: '0', found: '206529201'

Test #6:

score: 5

Accepted

time: 556ms

memory: 62872kb

input:

output:

13 116 1159 11577 150385 1654119 16540031 198480359 787928493 734581969 103223677 120676063 963754385 618704320 378636756 206516872 241703175 693677871 68103114 817225791 671888130 60162705 601476665 456558188 30918290 836035627 422508580 961059777 721412290 780076554 866081801 542037914 961741065 6...

result:

ok 399996 numbers

Test #7:

score: 5

Accepted

time: 671ms

memory: 58036kb

input:

7
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 0
5 2 2 0
5 2 2 0
7 1 1 0
8 1 1 0
6 1 1 0
7 3 3 0
9 3 3 0
12 2 2 0
10 2 2 0
13 1 1 0
13 4 4 0
13 7 7 0
15 1 1 0
15 7 7 0
16 7 7 0
19 1 1 0
18 8 8 0
19 2 2 0
23 1 1 0
23 5 5 0
24 8 8 0
23 6 6 0
27 3 3 0
28 4 4 0
26 12 12 0
29 6 6 0
30 1 1 0
31 12 12 0
30 9 9 0...

output:

1 1 1 21 1 376 9022 162020 2 1 3879458 77588784 1 475771479 9043 1 475771500 836010287 21 836010287 21 723456114 723627157 3879458 171043 462547233 193433576 974019581 162021 821331611 162021 376 162020 686601685 418942555 31199510 217891022 462547233 836010287 944144826 217891022 575663750 44315401...

result:

ok 399996 numbers

Test #8:

score: 5

Accepted

time: 535ms

memory: 63280kb

input:

8
4
100000
1 1 1 0
2 2 2 0
3 2 2 1
4 2 2 2
5 3 3 0
6 6 6 2
7 1 1 6
8 8 8 2
9 1 1 6
10 2 2 3
11 4 4 2
12 6 6 5
13 2 2 11
14 1 1 6
15 7 7 4
16 7 7 3
17 14 14 15
18 12 12 12
19 17 17 3
20 20 20 11
21 5 5 7
22 12 12 3
23 14 14 10
24 3 3 1
25 23 23 10
26 5 5 18
27 5 5 25
28 18 18 1
29 2 2 14
30 23 23 3
3...

output:

7 13 12 5 18 5 4 25 24 29 33 29 24 24 73 48 24 50 50 37 89 89 60 125 36 23 23 68 39 39 35 23 23 52 52 45 38 14 9 9 9 9 9 9 9 42 9 67 44 9 2 11 2 2 106 106 106 106 174 167 99 92 126 97 145 165 158 90 239 189 180 143 143 114 90 90 279 90 203 322 313 261 237 223 134 90 90 233 90 90 90 90 163 154 131 94...

result:

ok 399996 numbers

Test #9:

score: 5

Accepted

time: 581ms

memory: 57096kb

input:

9
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
3 1 1 0
4 2 2 1
6 2 2 2
6 1 1 2
8 3 3 2
9 1 1 4
8 4 4 0
9 4 4 0
12 6 6 3
13 3 3 4
13 6 6 3
15 5 5 0
15 2 2 7
15 4 4 2
17 5 5 2
18 5 5 0
18 4 4 6
19 2 2 8
22 8 8 9
23 3 3 10
24 6 6 12
25 7 7 13
24 1 1 11
27 3 3 7
27 12 12 2
28 4 4 0
30 3 3 9
31 15 15 15
32 1 1 7
31 ...

output:

1 1 15 1 14 0 13 57 0 1 42 27 0 39 13 11 114 83 57 0 26 26 26 0 0 26 26 14 52 26 26 26 0 11 15 0 11 68 11 11 78 26 11 11 0 230 0 0 203 203 0 0 203 189 0 39 189 137 0 52 241 0 0 252 199 188 26 188 52 0 110 26 110 110 95 0 57 22 27 11 11 27 166 11 155 0 344 0 138 39 0 116 115 22 0 314 115 198 115 198 ...

result:

ok 399996 numbers

Test #10:

score: 0

Time Limit Exceeded

input:

10
4
100000
1 1 1 0
2 1 1 0
3 3 3 0
4 3 4 0
5 3 5 0
6 1 4 0
7 5 5 0
8 5 7 0
9 3 6 0
10 6 10 0
11 1 2 0
12 8 11 0
13 4 12 0
14 2 12 0
15 7 10 0
16 6 8 0
17 13 15 0
18 8 9 0
19 2 6 0
20 8 14 0
21 3 18 0
22 11 18 0
23 5 11 0
24 6 12 0
25 3 24 0
26 13 23 0
27 3 8 0
28 14 22 0
29 4 26 0
30 1 5 0
31 13 17...

output:

result:

Test #11:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #13:

score: 0

Time Limit Exceeded

input:

13
4
100000
1 1 1 0
2 1 2 1
3 1 2 2
4 1 3 2
5 1 5 4
6 1 4 4
7 6 6 1
8 3 7 5
9 3 4 4
10 5 6 2
11 6 9 4
12 5 11 9
13 1 3 4
14 6 10 10
15 4 6 8
16 3 8 6
17 1 9 3
18 3 13 8
19 3 11 10
20 2 4 11
21 12 13 0
22 13 17 20
23 9 17 1
24 10 11 16
25 22 25 9
26 5 9 4
27 12 27 26
28 13 13 22
29 8 23 1
30 21 23 19...

output:

25 24 23 48 23 122 194 169 239 285 214 96 47 47 192 1948 2182 1132 385 216 455 47 1507 94 94 4391 21 779 12291 4368 12636 12422 2879 20926 11305 1734 1734 12241 12120 8241 2363 998243402 998243402 2730 11306 91111 1247 10884 30060 150 236313 234876 150813 176786 175374 223267 223051 998243520 61010 ...

result:

Test #14:

score: 0

Time Limit Exceeded

input:

output:

314675291 314677807 68 67 314677808 314658440 944033422 314680621 314675291 337 314675357 629358428 314647576 200 313797656 314680620 131 313786244 313805239 314647507 131 313596222 313797117 313805375 313797252 627604038 1939 313590060 314647440 313596759 200134819 62 942258054 6321 312754348 6059 ...

result:

Test #15:

score: 0

Time Limit Exceeded

input:

output:

439067562 439068484 318959252 46 878136042 439068483 439066200 44 318961097 310 439016734 439067605 439031659 878136965 220 439067559 439068481 439031569 440 40 878136964 40 439042788 438708079 3472 439016687 438418957 438617963 438618314 2233 438707769 438618359 1478 1478 438283335 438130747 438617...

result:

Test #16:

score: 0

Time Limit Exceeded

input:

output:

250424210 250425770 250425771 60 243671977 295 250424210 500851541 243604774 487351388 1120 243501137 243679351 487107962 243679351 1468 487358762 243679411 487351327 732467152 998244345 171 6951 245108450 243482407 14291 242852446 10637 198017982 9324 240915378 690699758 250424209 241938762 49220 2...

result:

Test #17:

score: 0

Time Limit Exceeded

input:

output:

704245756 54 704260865 410262264 704247213 526571265 53 348881665 704240983 116253118 936848639 159 410277374 704248854 316 704260862 704239291 704260861 704260861 50 704260861 48 704217212 704237967 364 704239448 510 704181242 704239448 48 317 704213998 704077303 208 844 704181350 704099337 7039554...

result:

Test #18:

score: 0

Time Limit Exceeded

input:

18
4
100000
1 1 1 0
1 1 1 0
3 1 2 1
2 1 2 0
2 2 2 0
5 1 3 1
6 1 1 1
6 2 3 2
6 1 3 2
9 1 4 1
10 2 3 1
12 1 3 0
10 1 4 2
11 2 5 0
12 4 5 1
14 2 4 1
15 5 6 2
16 4 5 5
18 3 3 5
18 1 6 4
18 3 4 4
21 2 4 3
21 4 7 4
23 7 9 3
23 1 5 3
25 3 5 3
26 5 6 2
25 1 7 4
29 3 4 6
30 4 11 2
29 1 3 3
29 1 5 6
32 9 12 0...

output:

47 233744468 233745501 233742714 44 233744514 233387066 40 233388909 1980 233389089 700520660 233742713 1928 233485974 467131618 1796 233615102 233247226 1748 233387066 25766 231134545 25610 229067820 227152938 231138322 23590 225210137 227182563 24572 227149261 221267489 42583 227149261 224588831 9...

result:

Test #19:

score: 0

Time Limit Exceeded

input:

output:

539086146 539096229 43 539096229 539086789 539096228 472 538906662 79948104 538915747 384 538915747 539086615 159240324 1712 698194975 856 812 777893115 297 8771 538232622 538907133 537633670 6883 78898948 538231635 537241005 3591 979 537641838 537553605 121 533822474 26040 533856530 531557507 4314 ...

result:

Test #20:

score: 0

Time Limit Exceeded

input:

output:

542502045 44 542502750 43 542500827 542502749 42 542499391 41 172 85 542494145 542489411 41 542492303 816 542317417 542274702 1071 542353364 814 542353276 345 542393245 542410067 1102 542202564 889 10513 541723364 542202947 5122 541491205 2378 540492214 3637 540872514 3508 541236404 541491673 2394 5...