QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#761766#8237. Sugar Sweet IITx_LcyTL 143ms23104kbC++141.3kb2024-11-19 10:03:272024-11-19 10:03:28

Judging History

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

  • [2024-11-19 10:03:28]
  • 评测
  • 测评结果:TL
  • 用时:143ms
  • 内存:23104kb
  • [2024-11-19 10:03:27]
  • 提交

answer

//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define add(x,y) (x=((x+y>=mod)?(x+y-mod):(x+y)))
int const N=5e5+10,mod=1e9+7;
int n,a[N],b[N],w[N],fac[N],inv[N];bool tg;
inline int qpow(int a,int b){int res=1;while (b){if (b&1) res*=a,res%=mod;a*=a,a%=mod,b>>=1;}return res;}
inline void solve(){
	cin>>n;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n) cin>>b[i];
	rep(i,1,n) cin>>w[i];
	rep(i,1,n)
		if (a[i]<a[b[i]]) cout<<(a[i]+w[i])%mod<<' ';
		else if (b[i]==i || a[i]>=a[b[i]]+w[b[i]]) cout<<a[i]<<' ';
		else{
			int cnt=1,gl=0,tg=1,x=b[i];
			map<int,int>vis;
			while (!vis[x]){
				vis[x]=1,++cnt;
				if (b[x]==x || a[x]>=a[b[x]]+w[b[x]]){
					if (cnt==2) gl=0;
					break;
				}
				if (a[x]<a[b[x]]){
                    add(gl,inv[cnt]);
                    break;
                }
				x=b[x];
			}
			cout<<(a[i]+gl*w[i]%mod)%mod<<' ';
		}
	cout<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	fac[0]=1;
	rep(i,1,N-1) fac[i]=fac[i-1]*i%mod;
	inv[N-1]=qpow(fac[N-1],mod-2);
	per(i,N-2,0) inv[i]=inv[i+1]*(i+1)%mod;
	int t=1;
	cin>>t;
	while (t--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 17336kb

input:

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

output:

500000007 5 5 6 
5 10 9 
166666673 5 6 
500000006 4 3 4 5 

result:

ok 15 numbers

Test #2:

score: 0
Accepted
time: 107ms
memory: 17260kb

input:

50000
5
508432375 168140163 892620793 578579275 251380640
3 4 4 1 3
346232959 736203130 186940774 655629320 607743104
1
863886789
1
364158084
18
864679185 463975750 558804051 604216585 694033700 499417132 375390750 337590759 467353355 111206671 983760005 984444619 322277587 138763925 205122047 97736...

output:

854665334 904343293 590444253 906393935 859123744 
863886789 
871186919 814243920 968784984 206455474 17527050 449261413 196759729 901433117 519383814 907574792 983760005 984444619 489899014 435736558 113628626 977360756 482247153 963066959 
665922935 577926775 132646723 421298438 601054667 99438820...

result:

ok 500000 numbers

Test #3:

score: 0
Accepted
time: 112ms
memory: 16788kb

input:

5000
32
770948244 768935990 679008477 140059459 126718762 172369567 60723299 139563987 671220914 149354390 157693423 281776861 412464718 869245476 446234952 827569915 294423239 672541652 309942421 252597259 603376135 207343159 409718246 366254256 59153054 589167713 171168426 802508752 545258815 7373...

output:

351791786 607445427 53351025 96277100 671164280 94237502 491532542 689573864 38427324 382704130 816373728 309284273 690430261 869245476 291526004 827569915 99656414 748890295 609504084 467918578 603376135 501064338 501009010 85120176 17055939 969361082 892391697 802508752 545258815 333168524 1165920...

result:

ok 500000 numbers

Test #4:

score: 0
Accepted
time: 110ms
memory: 16048kb

input:

500
831
941014154 653817226 737317394 548891909 650240324 784152288 337897920 919008275 807254058 243382923 935726688 583553418 88833789 750399807 577623567 595406246 982133524 532836513 286249019 780939608 102125785 501372622 567570217 761966021 24185161 261377492 548514161 60622277 424507766 53868...

output:

230438528 510098604 738011151 548891909 580268181 784152288 162823835 919008275 807254058 787780699 169718491 688535564 555077367 834193932 577623567 199204617 982133524 727940533 893934195 780939608 85179822 570950549 313144085 761966021 26675845 421401245 433344217 526647729 682184775 211847212 73...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 106ms
memory: 21564kb

input:

50
15547
79925051 123631785 451773599 290189979 8044136 985464173 25844832 289071231 239507420 289791589 915514277 479789432 442504231 802244771 740816861 403881580 976651260 224945729 212313439 170590725 774102963 484364764 878553828 980521523 949147335 322115091 853616905 280879526 946658136 41530...

output:

284534137 370503506 451773599 700040615 326578027 985464173 354118840 239415089 726041909 289791589 556747412 978820837 939334538 802244771 214118527 173005433 375935904 451502781 253004725 744007077 774102963 484364764 542287768 980521523 949147335 322115091 853616905 154636248 189607066 65863811 8...

result:

ok 500000 numbers

Test #6:

score: 0
Accepted
time: 134ms
memory: 21736kb

input:

5
323943
564718673 657489855 373282330 667584659 850348020 593942770 903492853 897217447 211655411 409828915 29599937 288981803 845363118 245960658 704846394 990499066 857206811 623803672 777109873 572212135 214230853 504844223 538282312 203265013 863644873 788795254 168640248 169295455 678434394 38...

output:

204335171 290429080 749926264 271550943 90669489 593942770 395887561 897217447 1122646 649466642 138487066 705990516 34851501 408992627 704846394 990499066 593266173 831686749 216979707 572212135 604730070 581128644 538282312 915779172 863644873 788795254 107879446 16737318 389993995 484044594 99298...

result:

ok 500000 numbers

Test #7:

score: 0
Accepted
time: 143ms
memory: 23104kb

input:

1
500000
167959139 634074578 773386884 503722503 2087506 443917727 691952768 150414369 45277106 674936674 279198849 421436316 140515506 451394766 695984050 254786900 17672277 228874183 25408976 166546966 609238004 783615461 523051181 854261286 433389755 773727734 127680943 43034811 892657961 4051531...

output:

504430027 374470866 773386884 605046474 48849004 443917727 489848651 669510599 807540660 887381332 434390308 135903469 373981470 557045185 817416129 330927981 295776527 272925008 971275424 706959112 736278170 783615461 722484387 90619431 433389755 621669631 773800724 379052020 48101859 531350264 344...

result:

ok 500000 numbers

Test #8:

score: 0
Accepted
time: 117ms
memory: 16940kb

input:

500000
1
641679119
1
46363815
1
409126743
1
301850965
1
479434398
1
8087428
1
411052661
1
274814245
1
186109822
1
557051627
1
832961130
1
468245461
1
885774901
1
205966212
1
640022376
1
40112818
1
451543633
1
116777249
1
301353585
1
865639134
1
978071440
1
696105130
1
54386476
1
950481378
1
64069307...

output:

641679119 
409126743 
479434398 
411052661 
186109822 
832961130 
885774901 
640022376 
451543633 
301353585 
978071440 
54386476 
640693072 
310901737 
164748344 
943205363 
136533544 
727803925 
460499039 
232286575 
665455084 
837511803 
315243095 
26199131 
205377168 
16924774 
899338264 
331544...

result:

ok 500000 numbers

Test #9:

score: 0
Accepted
time: 134ms
memory: 21480kb

input:

10
994
192416571 736204386 760505341 281487941 959877974 851233214 663685576 509485978 365899785 537198264 317546803 126718048 460789228 897818658 18680833 984634479 787676854 563354285 458421086 514363741 55602674 442874164 399256047 391675537 579236972 193191514 216578877 252675142 31271148 194871...

output:

80356619 157454092 293206050 6022041 731069905 151604390 514334525 563895392 669575403 774624127 317546803 558641523 992472593 125739893 949366972 984634479 881030593 213655841 746280399 717378810 243072174 891873405 399256047 391675537 579236972 807047987 154410058 377650673 806701544 229640743 643...

result:

ok 500000 numbers

Test #10:

score: -100
Time Limit Exceeded

input:

10
4059
462418415 299614005 191197342 44762066 300901267 961385491 493309329 213597634 708323640 936922772 23497231 461479602 140639435 670254967 996272440 567967593 778428919 911913371 691558703 798524068 217290311 543452971 177158172 239882043 702125314 764626435 303826249 933606746 990809366 4915...

output:

462418415 299614005 191197342 44762066 300901267 961385491 493309329 213597634 708323640 936922772 23497231 461479602 140639435 670254967 996272440 567967593 778428919 911913371 691558703 798524068 217290311 543452971 177158172 239882043 702125314 764626435 303826249 933606746 990809366 491533949 60...

result: