QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720039#9608. 皮鞋的多项式Kevin530750 1759ms311688kbC++206.8kb2024-11-07 10:22:462024-11-07 10:22:46

Judging History

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

  • [2024-11-07 10:22:46]
  • 评测
  • 测评结果:50
  • 用时:1759ms
  • 内存:311688kb
  • [2024-11-07 10:22:46]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
#include <immintrin.h>
#include <stdint.h>
//#pragma GCC optimize("O2")
using namespace std;
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rsrt(x) sort(rALL(x))
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
#define sz(v) (int)((v).size())
void die(string S){puts(S.c_str());exit(0);}
namespace Polynomial
{
	using ll=long long;
	using poly=vector<ll>;
	const ll mod=998244353;
	ll ksm(ll a,ll b)
	{
		ll ans=1;
		while(b)
		{
			if(b&1) ans=ans*a%mod;
			b>>=1;
			a=a*a%mod;
		}
		return ans;
	}
	const poly operator +(const poly &a,const poly &b)
	{
		int p=sz(a),q=sz(b);
		int n=max(p,q);
		poly ret(n,0);
		for(int i=0;i<n;i++)
		{
			if(i<p) ret[i]+=a[i];
			if(i<q) ret[i]+=b[i];
			if(ret[i]>=mod) ret[i]-=mod;
		}
		return ret;
	}
	const poly operator -(const poly &a,const poly &b)
	{
		int p=sz(a),q=sz(b);
		int n=max(p,q);
		poly ret(n,0);
		for(int i=0;i<n;i++)
		{
			if(i<p) ret[i]+=a[i];
			if(i<q) ret[i]+=mod-b[i];
			if(ret[i]>=mod) ret[i]-=mod;
		}
		return ret;
	}
	poly operator *(poly a,poly b)
	{
		if(max(sz(a),sz(b))<=250||min(sz(a),sz(b))<=50)
		{
			vector<longer> ret(sz(a)+sz(b)-1);
			for(int i=0;i<sz(a);i++)
				for(int j=0;j<sz(b);j++)
					ret[i+j]+=a[i]*b[j];
			poly res;
			for(auto x:ret) res.pb(x%mod);
			return res;
		}
		const ll g=3;
		int len=sz(a)+sz(b);
		int m=1;
		while(m<sz(a)+sz(b)) m*=2;
		a.resize(m);
		b.resize(m);
		vector<int> rev(m);
		for(int i=0;i<m;i++)
			rev[i]=(rev[i>>1]>>1)|((i&1)*(m>>1));
		for(int i=0;i<m;i++)
			if(rev[i]<i)
			{
				swap(a[i],a[rev[i]]);
				swap(b[i],b[rev[i]]);
			}
		for(int i=1;i<m;i<<=1)
		{
			ll gn=ksm(g,(mod-1)/i/2);
			for(int j=0;j<m;j+=(i<<1))
			{
				ll g0=1;
				for(int k=0;k<i;k++,g0=g0*gn%mod)
				{
					{
						ll x=a[j+k],y=g0*a[i+j+k]%mod;
						a[j+k]=(x+y)%mod;
						a[i+j+k]=(x+mod-y)%mod;
					}
					{
						ll x=b[j+k],y=g0*b[i+j+k]%mod;
						b[j+k]=(x+y)%mod;
						b[i+j+k]=(x+mod-y)%mod;
					}
				}
			}
		}
		for(int i=0;i<m;i++)
			a[i]=a[i]*b[i]%mod;
		for(int i=0;i<m;i++)
			if(rev[i]<i)
				swap(a[i],a[rev[i]]);
		for(int i=1;i<m;i<<=1)
		{
			ll gn=ksm(g,(mod-1)/i/2*(mod-2));
			for(int j=0;j<m;j+=(i<<1))
			{
				ll g0=1;
				for(int k=0;k<i;k++,g0=g0*gn%mod)
				{
					ll x=a[j+k],y=g0*a[i+j+k]%mod;
					a[j+k]=(x+y)%mod;
					a[i+j+k]=(x+mod-y)%mod;
				}
			}
		}
		ll val=ksm(m,mod-2);
		for(int i=0;i<m;i++)
			a[i]=a[i]*val%mod;
		a.resize(len-1);
		return a;
	}
	poly inv(poly p,int deg)
	{
		p.resize(deg);
		if(deg==1) return {ksm(p[0],mod-2)};
		poly w=inv(p,(deg+1)/2);
		poly g=w+w-p*w*w;
		g.resize(deg);
		return g;
	}
	poly deriv(poly p)
	{
		for(int i=0;i<sz(p);i++)
			p[i]=p[i]*i%mod;
		p.erase(p.begin());
		return p;
	}
	poly integ(poly p)
	{
		p.insert(p.begin(),0);
		for(int i=0;i<sz(p);i++)
			p[i]=p[i]*ksm(i,mod-2)%mod;
		return p;
	}
	poly ln(poly p)
	{
		return integ(deriv(p)*inv(p,sz(p)));
	}
	poly exp(poly p,int deg)
	{
		p.resize(deg);
		if(deg==1)
			return {1};
		poly g=exp(p,(deg+1)/2);
		g=g*(poly{1}-ln(g)+p);
		g.resize(deg);
		return g;
	}
	const poly operator %(poly a,poly b)
	{
		if(sz(a)<sz(b)) return a;
		int n=sz(a),m=sz(b);
		int d=n-m+1;
		poly a2=a,b2=b;
		reverse(a2.begin(),a2.end());
		reverse(b2.begin(),b2.end());
		a2.resize(d);
		b2.resize(d);
		poly q=a2*inv(b2,d);
		q.resize(d);
		reverse(q.begin(),q.end());
		q=a-b*q;
		q.resize(m-1);
		return q;
	}
	const poly operator /(poly a,poly b)
	{
		if(sz(a)<sz(b)) return a;
		int n=sz(a),m=sz(b);
		int d=n-m+1;
		poly a2=a,b2=b;
		reverse(a2.begin(),a2.end());
		reverse(b2.begin(),b2.end());
		a2.resize(d);
		b2.resize(d);
		poly q=a2*inv(b2,d);
		q.resize(d);
		reverse(q.begin(),q.end());
		return q;
	}
}
using namespace Polynomial;
const int B=250;
int n,q;
poly f[100100];
vector<int> G[100100];
int key[100100];
int s[100100];
poly g[100100],h[100100],p[100100];
vector<int> vk;
int d[500500],fat[500500],tp[500500],son[500500],siz[500500],in[500500],out[500500],dfn;
int ind[500500];
void dfs1(int u,int fa)
{
	fat[u]=fa;
	d[u]=d[fa]+1;
	siz[u]=1;
	for(auto v:G[u])
		if(v!=fa)
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])
				son[u]=v;
		}
}
void dfs2(int u,int fa)
{
	in[u]=++dfn;
	if(!tp[u]) tp[u]=u;
	if(son[u])
	{
		tp[son[u]]=tp[u];
		dfs2(son[u],u);
	}
	for(auto v:G[u])
		if(v!=fa&&v!=son[u])
			dfs2(v,u);
	out[u]=dfn;
}
inline int lca(int u,int v)
{
	while(tp[u]!=tp[v])
	{
		if(d[tp[u]]<d[tp[v]]) swap(u,v);
		u=fat[tp[u]];
	}
	if(d[u]<d[v]) return u;
	return v;
}
void dfs(int u,int fa)
{
	s[u]=sz(f[u]);
	for(auto v:G[u])
		if(v!=fa)
		{
			dfs(v,u);
			s[u]+=s[v];
		}
	if(s[u]>B)
	{
		vk.pb(u);
		key[u]=1;
		s[u]=0;
	}
}
poly calc(int u,int fa,int l,int r)
{
	if(l==r)
	{
		if(G[u][l]==fa) return {1};
		return g[G[u][l]];
	}
	int mid=(l+r)/2;
	return calc(u,fa,l,mid)*calc(u,fa,mid+1,r);
}
ll sum[100100];
void dfs3(int u,int fa)
{
	vector<int> vec;
	for(auto v:G[u])
		if(v!=fa)
		{
			dfs3(v,u);
			ind[u]+=ind[v];
			if(ind[v])
				vec.pb(ind[v]);
		}
	if(key[u])
	{
		g[u]={1};
		h[u]=f[u]*calc(u,fa,0,sz(G[u])-1);
		if(sz(vec))
		{
			auto calc2=[&](auto calc2,int l,int r)->poly
			{
				if(l==r) return h[vec[l]];
				int mid=(l+r)/2;
				return calc2(calc2,l,mid)*calc2(calc2,mid+1,r);
			};
			h[u]=h[u]*calc2(calc2,0,sz(vec)-1);
		}
		ind[u]=u;
		p[u]=h[u];
		for(int i=1;i<sz(p[u]);i++)
			p[u][i]=(p[u][i]+p[u][i-1])%mod;
	}
	else
		g[u]=f[u]*calc(u,fa,0,sz(G[u])-1);
	sum[u]=accumulate(ALL(g[u]),0ll)%mod;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		int k;
		cin>>k;
		f[i].resize(k+1);
		for(auto &x:f[i])
			cin>>x;
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs1(1,0);
	dfs2(1,0);
	dfs(1,0);
	vector<int> nvk;
	vk.pb(1);
	for(auto x:vk)
		for(auto y:vk)
			nvk.pb(lca(x,y));
	srt(nvk);
	uni(nvk);
	for(auto x:nvk)
		key[x]=1;
	vk=nvk;
	dfs3(1,0);
	int lst=0;
	h[0]={1};
	p[0]={1};
	while(q--)
	{
		int x,l,r;
		cin>>x>>l>>r;
		x^=lst;
		l^=lst;
		r^=lst;
		ll sum=0;
		for(int i=0;i<sz(g[x]);i++)
		{
			int l1=max(0,l-i);
			int r1=min(sz(p[ind[x]])-1,r-i);
			if(l1>r1) continue;
			if(l1) sum=(sum+g[x][i]*(p[ind[x]][r1]-p[ind[x]][l1-1]+mod))%mod;
			else sum=(sum+g[x][i]*p[ind[x]][r1])%mod;
		}
		lst=sum;
		cout<<lst<<'\n';
	}
	return 0;
}

詳細信息

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 42ms
memory: 8680kb

input:

1977 200000
0 883734638
1 497045124 50605999
0 467033353
8 514303373 873913661 21585656 827572829 831599042 669912647 980444584 921677622 90967524
0 111009203
0 980468811
1 965285721 647475291
0 55665482
0 810210109
5 99482052 915734955 536563337 860629716 489661090 127640528
4 452261176 414532348 8...

output:

0
0
0
1462214
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
709010908
0
0
0
0
0
0
0
0
0
0
0
0
0
0
362560754
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
887205253
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
532388854
0
0
0
0
0
0
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 200000 numbers

Test #2:

score: 7
Accepted
time: 40ms
memory: 11012kb

input:

1969 200000
1 928278040 49291189
0 106316044
7 355985609 701602147 528629206 472008316 626845782 871506163 793475066 634852555
0 193911795
1 498772599 387035156
2 244940676 15788848 225049996
8 257966353 171785747 687353797 643745787 25069581 248781417 212047281 295151595 525248876
2 606862291 21936...

output:

0
0
702752596
0
0
0
564436252
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
539882987
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
421207407
0
0
0
0
0
...

result:

ok 200000 numbers

Test #3:

score: 7
Accepted
time: 40ms
memory: 12856kb

input:

2000 200000
0 230695610
4 400302240 129755410 740309716 633048240 594259574
2 261261651 610028309 279096898
0 306295327
1 411519353 880936332
4 458323735 111990362 693959473 50334178 49499787
0 451592459
1 114402580 931927324
4 639243873 254122580 669324541 571247271 275880979
0 440954066
1 43964805...

output:

0
0
801713754
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
807839363
0
845789441
0
0
0
0
0
0
0
0
180971215
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
791867965
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
514100741
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
995968989
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8782...

result:

ok 200000 numbers

Test #4:

score: 7
Accepted
time: 50ms
memory: 11356kb

input:

1978 200000
1 191987956 540466676
1 120742551 206257774
2 744430486 875250521 181042024
0 103091601
0 304724279
0 649017453
0 145685556
0 599144446
0 364188280
0 57833875
3 414338956 791946816 770890256 830048461
0 819249191
0 755199883
1 758814940 693449562
1 280052104 142092003
0 214207528
0 85521...

output:

0
0
0
0
0
0
0
0
0
0
0
0
574798441
0
0
551851346
0
0
0
0
0
0
298923018
0
0
0
0
0
706319639
0
0
932127532
0
0
0
0
506810290
0
0
375480684
0
0
0
0
0
575707276
0
769974190
0
0
0
0
0
0
0
0
0
255132253
234643792
0
436442475
0
0
0
0
0
0
770777820
0
0
0
0
382421721
0
0
10702740
0
0
912641116
0
679541132
0
0...

result:

ok 200000 numbers

Test #5:

score: 7
Accepted
time: 43ms
memory: 11052kb

input:

1997 200000
1 609381747 833571580
1 102342468 526127035
1 880931004 909374728
2 103826707 729151512 34293902
1 273372046 293953096
0 554926428
0 676458000
1 401799287 357803550
1 695810053 794616522
0 748711966
1 967175820 34877055
2 257806263 264285746 818013686
1 576641758 75701100
0 795476926
0 7...

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
996352329
0
0
0
0
61024835
0
0
424430639
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
392760029
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
442026045...

result:

ok 200000 numbers

Subtask #2:

score: 3
Accepted

Test #6:

score: 3
Accepted
time: 111ms
memory: 34072kb

input:

98154 200000
0 948053956
0 149079029
0 871940052
0 888807640
0 284687863
0 760258916
0 916765457
0 121680504
0 210430381
0 162441114
0 640680402
0 269559148
0 706423649
0 619089994
0 776236890
0 44769489
0 863235377
0 283984837
0 251593760
0 863377054
0 40488948
0 100272768
0 628132233
0 18841959
0 ...

output:

0
160622568
939846745
221659137
0
312930382
620657950
975124531
0
241389446
233242086
656904774
0
666641212
127400637
0
0
61866892
388266897
17714856
158666308
181172732
0
231863345
0
0
993493871
0
945624744
0
53582097
0
553931157
940627115
0
864491900
0
0
910285591
0
0
0
0
810021023
0
957355731
870...

result:

ok 200000 numbers

Test #7:

score: 3
Accepted
time: 116ms
memory: 33996kb

input:

98566 200000
0 209181684
0 889317979
0 925862494
0 861680823
0 629292192
0 781545895
0 58892045
0 300501945
0 510137985
0 764792857
0 551445762
0 771899874
0 828696971
0 260462870
0 535761660
0 532161459
0 187099
0 691412616
0 891055462
0 283180276
0 446617517
0 928434806
0 974119517
0 895921491
0 8...

output:

0
541915644
0
0
0
344789573
37160095
0
0
378148422
0
27407348
0
510146116
0
0
593724632
308323897
0
208041958
834526238
308130263
413718362
0
0
452600858
215844992
0
0
138748183
0
597752749
0
0
0
131857104
0
0
583969453
644145934
277456647
0
730806159
210434799
329144450
0
271266199
0
0
532721033
33...

result:

ok 200000 numbers

Subtask #3:

score: 0
Time Limit Exceeded

Test #8:

score: 0
Time Limit Exceeded

input:

97330 200000
2 356080749 854511831 888131963
0 533633039
0 260190631
0 217335008
2 998111375 903316988 891866314
0 507509609
0 556810297
1 190927168 988903728
1 270553180 387224380
0 360295480
0 775464651
0 755424805
0 71030175
0 690904984
0 702271750
0 360541906
0 903384679
0 769283169
0 6990072
0 ...

output:


result:


Subtask #4:

score: 20
Accepted

Test #13:

score: 20
Accepted
time: 1299ms
memory: 163820kb

input:

50000 50000
1 610345459 691411093
1 476654936 529767753
1 8856530 640833948
1 961473497 456987897
1 462733802 114971681
1 662244461 415955667
1 717992437 907944693
1 346097988 176526535
1 805826501 182409272
1 33105050 971783530
1 45972429 258997374
1 964103067 796756441
1 958668755 735146502
1 9543...

output:

0
0
0
0
0
0
0
610268301
297428232
729194415
0
0
506964543
0
198345028
778136423
0
89695571
651093422
174709
799469987
0
0
0
0
374762615
64155221
0
644085102
355318236
625240586
0
0
0
0
611217681
0
246858712
0
946363040
766457000
0
0
0
0
0
0
0
885388926
324657374
0
0
608041499
0
0
0
595311003
0
0
790...

result:

ok 50000 numbers

Test #14:

score: 20
Accepted
time: 1676ms
memory: 287424kb

input:

50000 50000
1 284188823 730123812
1 578529655 782975708
1 682107201 169640319
1 504919829 297067490
1 126340369 681480864
1 702290552 331608873
1 89823300 900339069
1 661791786 696739097
1 146107507 457302386
1 309885170 133384173
1 1601509 445278250
1 82308245 611577805
1 575317 145972663
1 3340187...

output:

118484783
20950737
827095992
192485904
949696395
760932709
0
827083836
737333618
0
0
936633428
869751868
21893026
0
0
700825516
0
0
140717292
495143473
757971245
71851829
758042728
168032853
336898224
82834617
0
50295595
473191194
0
603695852
88648030
191908163
0
0
347045240
304736441
10279888
28050...

result:

ok 50000 numbers

Test #15:

score: 20
Accepted
time: 1072ms
memory: 136748kb

input:

50000 50000
1 908905842 879908939
1 69131120 893333490
1 766104239 502577285
1 598541702 20672714
1 19129534 562935613
1 17855501 931751363
1 817552765 924309216
1 601703730 928273412
1 280909912 198946276
1 259187488 350711225
1 460175073 829804287
1 142301100 182462131
1 440043596 503299121
1 4954...

output:

608336339
0
479640409
0
0
0
304101361
575455842
631421870
0
921143438
0
0
614891272
920725723
987924343
0
0
944939021
0
842440434
0
0
219630310
595973439
303974010
0
0
0
0
266178665
352670733
355014561
0
0
0
15870579
900144368
490797433
594447900
0
521603348
0
0
763764981
0
0
238461206
0
0
22187316
...

result:

ok 50000 numbers

Test #16:

score: 20
Accepted
time: 1557ms
memory: 209144kb

input:

50000 50000
1 132666924 481468407
1 233104347 925423798
1 196520221 188340478
1 880316330 347865528
1 362038740 586184357
1 260977445 869456691
1 413836428 997205621
1 925267833 389145261
1 412474208 605923400
1 275275170 580329557
1 248067291 201190325
1 267032222 546518461
1 60371460 731907388
1 2...

output:

284858974
0
521392986
0
0
419555545
0
279474735
869174793
0
0
0
0
327341031
0
887506929
253382960
0
549720153
0
470223182
448985266
0
0
0
571599922
0
0
0
0
687095778
0
0
523720173
340816378
0
927700876
0
0
0
117671213
493623216
0
269849900
992438456
0
233002506
0
875191758
582797638
0
0
222273961
0
...

result:

ok 50000 numbers

Test #17:

score: 20
Accepted
time: 1554ms
memory: 209644kb

input:

50000 50000
1 570249482 963041872
1 164483403 404765803
1 181145508 416450528
1 536381689 716629517
1 19355006 80481263
1 627992141 65443806
1 185587289 129800096
1 667577148 11179897
1 512133278 870239643
1 135475895 124891452
1 917154463 721424462
1 243207295 964207791
1 348452088 67572040
1 16668...

output:

76593910
267735832
0
0
379967837
128237686
782639460
0
0
155844091
934345203
666090547
241913187
0
0
884593508
0
199971361
0
876108660
362635493
0
0
0
0
93781856
635645613
903201788
0
794166948
108363160
0
0
937730015
0
641371731
0
836048882
0
584024075
0
0
0
0
169018859
0
0
0
0
984231395
0
0
102506...

result:

ok 50000 numbers

Test #18:

score: 20
Accepted
time: 1574ms
memory: 264244kb

input:

50000 50000
1 374439028 76801984
1 198570918 279646664
1 738529796 230017198
1 93739509 610640325
1 525884738 858818589
1 949692556 761814293
1 235726510 7565628
1 45230953 841809717
1 624654181 697155421
1 56572048 898846486
1 181498104 803293558
1 123843798 593520342
1 590491409 791005242
1 888374...

output:

864276436
440159890
536780052
321076766
468541452
986423750
663920928
988866764
260419539
0
0
0
0
917177790
340374136
783267120
861409101
702416442
365736645
250814244
0
889464570
0
158883242
778105434
403578126
718091928
0
110804297
685559904
0
17649876
0
811219235
0
320574087
469972593
932031629
3...

result:

ok 50000 numbers

Test #19:

score: 20
Accepted
time: 1375ms
memory: 178160kb

input:

50000 50000
1 33459023 378743148
1 649009512 322497285
1 4159024 354205478
1 635048826 663468389
1 822658913 27307310
1 195454131 803172665
1 875401287 11624886
1 289967362 733461614
1 251177354 546439677
1 600412174 876096433
1 230834162 878747260
1 269956920 918423510
1 254773805 746291985
1 29210...

output:

144329675
0
937010808
0
387987066
256520687
0
415222201
574050902
0
0
78330661
774146527
545659020
0
0
676856924
0
0
0
371281553
0
724389591
180883171
60120880
758706582
260395535
86733354
0
0
454943744
866940819
213813873
343349330
781027374
265021034
322573212
71290236
0
0
333346154
117482220
1005...

result:

ok 50000 numbers

Test #20:

score: 20
Accepted
time: 1759ms
memory: 311688kb

input:

50000 50000
1 740199008 613475557
1 922880359 842126974
1 451019859 922790230
1 178429894 72393602
1 569458862 898768795
1 834271550 7640899
1 645877613 459724785
1 15126535 700620044
1 546332191 981494527
1 693370057 48191032
1 599613461 710991225
1 560674975 816111048
1 324902849 638444457
1 41924...

output:

874743447
472418696
893475459
768083962
844890219
0
491167288
0
662057644
33125578
0
0
0
380253379
790862397
453081406
0
0
64445999
613775426
0
0
0
669660760
597392638
0
37758869
0
11684083
11431232
0
827641705
191050687
39123082
0
821861901
0
658965581
0
107926632
720677708
0
0
240074723
949362284
...

result:

ok 50000 numbers

Subtask #5:

score: 20
Accepted

Test #21:

score: 20
Accepted
time: 225ms
memory: 46944kb

input:

19854 20000
1 150513542 240180212
0 987796281
0 90054116
1 191708494 438440429
0 192815969
0 867402303
1 531762469 210966860
2 95662022 345368425 199338548
0 269135053
0 816253511
0 66854944
0 319745952
0 202288549
0 492853777
0 410846691
0 824737426
0 821545014
0 72050044
0 534080091
1 542636124 52...

output:

913323334
0
0
0
0
0
0
0
0
0
0
0
901017606
0
0
0
0
0
954099396
0
0
432419999
0
0
0
0
0
0
0
761082946
259729654
0
0
0
0
790235355
933098570
356668385
125624181
0
0
0
0
917034405
0
321407524
0
671256345
39032345
0
0
676929142
0
0
0
0
0
0
0
0
910494481
0
0
0
733125978
0
0
835461650
0
154343024
690428959...

result:

ok 20000 numbers

Test #22:

score: 20
Accepted
time: 157ms
memory: 38656kb

input:

19416 20000
1 813812350 62928444
2 446931520 455152410 865811291
1 483245225 719509880
0 10630578
1 722267364 499990463
0 978295677
0 524126644
2 398577038 701788899 939255653
0 945953310
0 358029034
1 54632159 541649711
0 714215963
0 760637762
1 792667329 540131052
1 336329275 197811762
0 594815129...

output:

0
0
0
0
0
0
0
0
691960524
0
0
0
0
0
0
0
0
0
0
917519575
0
0
0
0
457906160
686627668
0
263875204
0
0
0
860458574
0
0
197732443
0
0
0
0
0
0
0
0
0
0
0
0
0
619069496
0
0
145464796
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
409777622
309523189
862407937
0
0
954411456
0
0
0
0
0
0
304719397
0
548777971
176155...

result:

ok 20000 numbers

Test #23:

score: 20
Accepted
time: 216ms
memory: 41520kb

input:

19645 20000
1 738216072 655062389
0 478261419
28 38522218 205802590 608351714 423733656 368037127 943951223 529243126 691493532 378826276 32699256 849862664 799709335 113704178 671006657 736000878 683394539 338518052 850384023 536423162 225738416 276528868 965415989 455460104 274736758 547583027 423...

output:

0
710035374
349663621
61124181
0
0
0
0
0
0
0
0
0
0
0
0
0
0
694466943
0
0
0
0
103025366
0
0
108158012
0
0
898653012
0
0
0
0
124734988
0
628306562
0
0
0
0
0
829055370
0
942321667
0
0
0
0
100614270
0
666765805
277413825
0
0
0
0
492192785
0
0
0
0
517011159
0
0
0
0
172598073
0
258513717
233404540
8590182...

result:

ok 20000 numbers

Test #24:

score: 20
Accepted
time: 200ms
memory: 36200kb

input:

19847 20000
4 815026590 930615671 256423615 192058090 553677398
0 854407447
3 121205405 14847480 141687199 287623506
2 379798536 291209656 593839232
1 352031200 841240984
0 295186159
0 841042115
0 679392127
0 420742492
2 891756622 260075296 417909411
0 645458804
0 681889229
0 29119165
0 99142741
3 7...

output:

470171472
213398321
0
0
55462715
0
338144412
0
0
0
0
0
0
0
698725184
0
0
0
0
47366191
0
317326831
0
0
0
239746199
214366720
0
0
0
0
0
279091720
0
86836316
0
0
0
35432299
0
308555884
0
319326811
0
0
0
305535605
0
358646410
0
0
131375996
0
0
0
0
0
0
0
0
570823027
0
0
80022023
0
954809219
0
0
0
0
26917...

result:

ok 20000 numbers

Test #25:

score: 20
Accepted
time: 219ms
memory: 40084kb

input:

19990 20000
3 575964327 889968526 762346953 464212918
0 91433877
0 762285092
1 703259059 61874142
2 130773960 696187633 280576635
1 163442506 294293968
0 134582456
0 525908094
2 981613234 494831823 871173319
0 320232487
0 951459253
0 725136632
2 48590419 631199232 992008959
1 860836891 867326137
1 6...

output:

90336621
0
741001438
326700634
0
0
0
0
0
0
925215064
0
0
863889195
0
0
0
0
0
576304546
0
0
0
0
583889751
0
0
0
0
0
0
813389361
0
0
0
0
0
0
0
108311310
0
0
653689603
0
0
0
91295650
0
347062400
0
0
0
0
620038417
846141331
99345412
0
581988923
0
0
0
0
365053652
29464872
917029396
788177507
288943414
0
...

result:

ok 20000 numbers

Test #26:

score: 20
Accepted
time: 246ms
memory: 43992kb

input:

19302 20000
1 140879209 815790450
0 263312184
2 357492390 407721624 927753023
17 329030216 687250506 904721674 66559073 150996400 582272412 140464848 806623151 989399143 916248414 596527559 964780629 802988469 182625819 764316767 594475067 203564894 275476377
0 547777698
0 34169169
0 93303556
0 5807...

output:

0
0
132910965
0
127962650
0
453633700
0
0
451482843
0
0
0
388743057
0
0
293560154
874329518
0
0
0
0
0
0
0
0
0
0
766081674
0
0
234642116
0
0
669563153
0
748448386
0
0
0
0
0
0
0
0
0
670410122
87350607
0
416323263
174794844
0
0
0
0
0
0
196859095
0
0
0
0
644332981
0
0
0
0
0
0
0
0
0
469599960
0
0
0
0
931...

result:

ok 20000 numbers

Test #27:

score: 20
Accepted
time: 255ms
memory: 50244kb

input:

19653 20000
1 906614788 500628713
0 988012762
0 284902421
0 704468047
0 872560811
1 907887753 600402772
0 767950811
0 118754288
0 290736011
0 217729487
1 190172852 683598286
0 723859834
0 220112811
0 448174595
0 39653265
0 770732977
0 458450918
0 438730398
0 183195813
0 191514564
0 2928127
0 3007322...

output:

0
244727120
0
0
132988676
354295625
0
667761790
0
0
0
0
0
822615931
0
0
0
0
0
0
504618092
0
973780962
0
0
0
0
737475269
0
0
0
383245743
0
0
10261578
551768502
0
835642191
0
0
69015099
0
0
773914454
0
0
0
0
0
193232063
0
0
0
0
0
230203189
0
0
0
0
0
0
0
0
120778708
0
949822563
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 20000 numbers

Test #28:

score: 20
Accepted
time: 186ms
memory: 35860kb

input:

19072 20000
0 910136763
1 809343877 577693489
0 805540439
0 728993500
0 234081004
1 891104112 210354669
0 262384318
0 568913493
0 376708574
1 145377149 421745582
0 108964429
0 697119989
0 615671424
0 697025092
0 222804661
0 927317484
1 66775292 771115618
0 405877157
1 977355316 502648356
1 218406564...

output:

0
0
0
558272462
0
0
0
0
0
0
0
328733917
446478844
0
0
0
0
0
0
848724549
0
0
980511070
0
0
597411269
0
127279175
0
0
0
0
0
739852501
0
0
0
0
0
0
568449517
589452941
0
0
0
0
791777304
0
0
0
0
114744131
322763812
613885875
52417149
0
0
0
0
149449664
0
0
644257795
0
725958460
276312482
499158209
8075964...

result:

ok 20000 numbers

Test #29:

score: 20
Accepted
time: 28ms
memory: 49272kb

input:

20000 20000
0 614936162
0 182986322
0 40697275
0 824161988
0 240412566
0 287310162
0 63000758
0 958628891
0 139827408
0 971860786
0 325782161
0 726800064
0 392930207
0 911604309
0 904980384
0 508941069
0 641836609
0 759719860
0 732767740
0 94630498
0 390558752
0 764408563
0 40013248
0 414628626
0 87...

output:

664811563
788614780
974744409
578158051
972633254
83874056
204528292
473798071
213046046
429307018
595958938
227031150
671368761
461998185
115917717
744731293
465171055
551785804
318236143
171800659
801541585
707676156
58721393
116249265
334321741
90511883
550891644
284752711
828872978
231691412
450...

result:

ok 20000 numbers

Test #30:

score: 20
Accepted
time: 180ms
memory: 34364kb

input:

19446 20000
1 701024899 61691599
0 459112272
0 605953973
0 852714844
0 174821235
1 313026866 19060724
0 553043793
1 837260834 209473757
0 445224261
0 18895399
1 976728020 509710102
0 332645932
0 661618262
0 204178386
0 269435005
0 736889829
0 397995492
0 866964923
0 132403278
0 596284173
0 958984850...

output:

534451823
0
0
607037735
558413343
0
0
0
0
0
0
0
0
0
0
0
673258724
0
869080507
506727857
9843331
0
85465239
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
398060444
882747749
0
0
0
0
0
0
214087586
0
0
0
0
0
0
0
0
0
0
0
0
733471287
0
636321624
0
351918892
0
0
856397457
0
0
0
0
0
0
0
0
91532953
0
0
0
0
0
237024413
63...

result:

ok 20000 numbers

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%