QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207326#7558. Abstractucup-team266WA 56ms24568kbC++143.3kb2023-10-08 13:57:552023-10-08 13:57:55

Judging History

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

  • [2023-10-08 13:57:55]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:24568kb
  • [2023-10-08 13:57:55]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n;++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef array<int, 3> ai3;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 998244353;
const int inv2 = (Mod+1) / 2;
const int inv6 = (Mod+1) / 6;
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, int p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 100100;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
}
int binom(int n, int m){ return mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(ll &a, ll b){ (b>a) ? (a=b) : 0; }

int n, m;
const ull lmt = (1ull<<62) -1 ;
struct bigint{
	ull a[255];
	int len;
	bigint(int x = 0){ memset(a, 0, sizeof(a)), len = (bool)x, a[0] = x; }
} c[10010];

bigint operator +(bigint lh, bigint rh){
	bigint ret(0);
	ret.len = max(lh.len, rh.len);
	//rep(i, lh.len){ cout << lh.a[i] << " ";} cout << "+ "; rep(i, rh.len){ cout << rh.a[i] << " ";} cout << "= ";
	rep(i, ret.len) ret.a[i] += lh.a[i] + rh.a[i], ret.a[i+1] += ret.a[i] >> 62, ret.a[i] &= lmt;
	while(ret.a[ret.len]) ++ret.len;
	//rep(i, ret.len){ cout << ret.a[i] << " ";} cout << "\n";
	return ret;
}

bigint smallmul(bigint lh, int rh){
	bigint ret(0);
	if(!rh) return ret;
	ret.len = lh.len;
	ull car = 0;
	rep(i, ret.len + 1){
		__int128 cur = (__int128)lh.a[i] * rh + car;
		ret.a[i] = (ull)(cur & lmt);
		car = (ull)(cur >> 62);
	}
	while(ret.a[ret.len]) ++ret.len;
	return ret;
}

int a[10010];
vi rg[10010];
int deg[10010];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	rep(i, n) cin >> a[i];
	rep(i, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		++deg[u], rg[v].push_back(u);
	}

	queue<int> q;
	rep(i, n) if(!deg[i]) c[i] = bigint(1), q.push(i);
	while(!q.empty()){
		int u = q.front(); q.pop();
		rep(i, (int)rg[u].size()){
			int t = rg[u][i];
			c[t] = c[t] + c[u] + c[u];
			--deg[t];
			if(!deg[t]) q.push(t);
		}
	}

	bigint s = 0;
	rep(i, n) s = s + smallmul(c[i], a[i]);
	//rep(i, n){
	//	cout << i << ": ";
	//	for(int j = c[i].len-1; j >= 0; --j)
	//		cout << c[i].a[j] << " ";
	//	cout << "\n";
	//}
	int ans = 62 * (s.len - 1);
	//for(int j = s.len-1; j >= 0; --j){ cout << s.a[j] << " "; } cout << "\n";
	for(int i = 62; i >= 0; --i){
		if(s.a[s.len-1] >> i){
			ans += i+1;
			break;
		}
	}
	cout << ans << "\n";

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 23752kb

input:

3 2
1 1 1
1 2
2 3

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 23756kb

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #3:

score: 0
Accepted
time: 0ms
memory: 23696kb

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 41ms
memory: 24560kb

input:

7286 80481
637288250 628935175 588324396 766398783 663989874 865498593 695497968 630237220 19939888 448367842 412696777 111291257 304805809 585852799 58270069 391993802 606944382 827515045 389862501 643981354 160381074 324288921 257053597 980043955 417281046 870855665 360154617 60327683 966755927 55...

output:

7344

result:

ok 1 number(s): "7344"

Test #5:

score: 0
Accepted
time: 25ms
memory: 24240kb

input:

3485 69345
126919335 553087878 429357681 107790917 253972208 821989783 176128117 334722143 34989524 671942525 903789117 265616010 293291124 132216887 707703503 418751992 884191319 759015972 55466567 99122540 354621491 27107365 365748390 577882877 170254553 988104760 599408763 810052334 913007827 481...

output:

3552

result:

ok 1 number(s): "3552"

Test #6:

score: 0
Accepted
time: 17ms
memory: 24216kb

input:

4689 60385
379526147 320297565 290144701 411659092 808895255 349467622 912526797 945207025 147304164 611762485 690455633 593862503 349796612 915342714 685542590 669277310 101349964 538393690 204894013 843271709 963886266 502004930 826860359 607900073 348962474 135953765 54884804 334093983 550287693 ...

output:

4735

result:

ok 1 number(s): "4735"

Test #7:

score: 0
Accepted
time: 9ms
memory: 23900kb

input:

2025 13466
126370676 243460503 613061215 640378899 861853110 677538246 285817021 986777516 15580136 316176404 626530661 279208872 907269727 867851232 311220916 469724204 74428615 32310082 942939721 177419954 762441651 262073944 202700718 559297816 358074717 198943661 440995981 349418644 741410433 25...

output:

2067

result:

ok 1 number(s): "2067"

Test #8:

score: 0
Accepted
time: 0ms
memory: 23732kb

input:

121 199
896493283 602876262 190412813 539005355 361393375 336898107 57573022 860831181 796613695 697555446 474410296 573506583 646847982 775622764 433638751 410211736 706262484 308743162 694033299 787089776 557626422 410409760 666965625 606229683 774588923 213849175 739959306 318954654 193492757 624...

output:

153

result:

ok 1 number(s): "153"

Test #9:

score: 0
Accepted
time: 38ms
memory: 24476kb

input:

5173 82801
972178880 55787886 726219846 273505188 14833165 37678608 275433188 549410719 708739346 1596684 204453484 945870857 502585545 308710857 846757497 570148074 483775449 435833419 921907607 261743006 297037496 320466454 792975799 516106710 589464190 376914168 858666582 446429120 925757959 8940...

output:

5233

result:

ok 1 number(s): "5233"

Test #10:

score: 0
Accepted
time: 28ms
memory: 24400kb

input:

4451 68751
734143298 168118925 474566099 914135738 175189225 854565096 725921855 150734745 33215980 472643707 815730766 973287826 824133531 440222648 918212826 837679353 7350350 167875290 528553053 937486333 615587529 256295189 480035843 489273798 172853737 135811440 968971168 925087779 375176970 33...

output:

4514

result:

ok 1 number(s): "4514"

Test #11:

score: 0
Accepted
time: 20ms
memory: 24224kb

input:

2383 58762
509075060 867612403 21996053 527466121 553589454 671190283 764167183 890805913 862657253 922878788 744689887 170690927 609890819 40416579 350962700 185478150 75096314 104961883 754430815 421417968 778490115 468058225 431868239 303651678 581681467 384545786 339203220 559058549 941951463 37...

output:

2467

result:

ok 1 number(s): "2467"

Test #12:

score: 0
Accepted
time: 19ms
memory: 24168kb

input:

2001 67457
723197687 478813608 232810746 428945491 429136421 648852717 544540978 369132456 184435370 343975895 585223464 502157635 503001231 386021746 670322194 813441457 170390807 934181094 930734781 209174515 312012184 837865721 956809810 794424618 401909501 180498703 669648434 783741686 378051289...

output:

2102

result:

ok 1 number(s): "2102"

Test #13:

score: 0
Accepted
time: 17ms
memory: 24140kb

input:

9489 23514
202036366 696617402 38892756 337095695 965501524 948136577 612864889 980877872 264613206 879049290 604347121 920794549 640708344 587199470 185265444 98746351 581544222 927935481 643077470 812763147 38525503 654269070 256346123 899052544 92441646 264988076 66356031 292735115 922964957 3745...

output:

9521

result:

ok 1 number(s): "9521"

Test #14:

score: 0
Accepted
time: 25ms
memory: 24324kb

input:

9561 54289
98620438 516139680 658256456 902183713 624450302 546644345 93605161 13455288 650974201 859012671 775849200 862051631 839753906 309276811 504053052 106564927 917376230 455638053 499818452 348588006 293037448 892678488 109670419 100714558 133812448 189695864 759580899 825104942 225397418 66...

output:

9603

result:

ok 1 number(s): "9603"

Test #15:

score: 0
Accepted
time: 25ms
memory: 24312kb

input:

8673 41321
713852196 41672085 3578 76498661 193896234 880990702 92363180 297390233 877917509 781447228 559185392 628626089 309281217 479160612 538327677 495012807 230891929 947840408 760224668 4608905 590467332 636974494 563916969 835068689 590302247 655826457 532649798 125153559 521998114 401283582...

output:

8712

result:

ok 1 number(s): "8712"

Test #16:

score: 0
Accepted
time: 17ms
memory: 23976kb

input:

945 29713
352273400 865995982 176653085 727929352 606322564 54353211 560652092 950094104 35932743 672252257 608698156 714904143 464636830 446842133 793178441 165700304 587559973 210748888 475949161 525698243 604063691 220029563 329796511 754927076 272931162 465526795 932512075 597447389 346386244 67...

output:

1035

result:

ok 1 number(s): "1035"

Test #17:

score: 0
Accepted
time: 15ms
memory: 24176kb

input:

1601 43526
328657623 344662164 242182624 662893665 640466981 502913348 345497581 581438973 754099115 328827051 165687194 213281607 767975180 93816219 248298421 561877492 748929658 390895323 957073136 911088737 981351319 138160220 526659627 549050117 99010115 439572276 865895227 821112082 679833882 1...

output:

1692

result:

ok 1 number(s): "1692"

Test #18:

score: 0
Accepted
time: 28ms
memory: 24364kb

input:

8283 51577
942991980 827440413 493475089 923719536 882215143 372159216 789439259 268444689 192292947 207244213 764137033 10523178 947086322 393842511 834658105 514780495 317849618 422191383 819766666 854496034 788744341 703879894 802085844 216654060 446528313 426075265 739963640 984681283 368079365 ...

output:

8323

result:

ok 1 number(s): "8323"

Test #19:

score: 0
Accepted
time: 30ms
memory: 24392kb

input:

6535 61745
461883464 319967141 437979355 392664659 478849011 279140261 869286297 664092498 151063908 651453191 847691042 332414480 590562621 678469113 835313229 498830929 687038363 726868751 131933681 481236765 821004184 828928100 429856395 344702050 828374999 139181918 121900195 813753266 489199098...

output:

6579

result:

ok 1 number(s): "6579"

Test #20:

score: 0
Accepted
time: 28ms
memory: 24396kb

input:

1301 96001
360923566 504434045 568840592 149839072 672039632 442411522 70901261 641485201 511027097 242084208 945354144 993339776 118169822 39643622 183456405 133932691 954217434 865433622 809427908 633877391 342281786 230956039 463090342 328264297 242983917 158025716 769561000 893869221 468865309 9...

output:

1498

result:

ok 1 number(s): "1498"

Test #21:

score: 0
Accepted
time: 38ms
memory: 24424kb

input:

4561 81661
662903377 209601263 459486118 589651306 580105720 877383814 279419889 11603528 538188584 617963323 327968416 267897373 432601956 939666147 442933263 231175482 498451107 593220789 414643481 528796372 556876168 933236318 552381725 310145564 763857377 703961676 553121065 892630758 984717296 ...

output:

4638

result:

ok 1 number(s): "4638"

Test #22:

score: 0
Accepted
time: 14ms
memory: 24140kb

input:

7671 27811
344667830 466488589 713489595 881419363 661677016 253276616 503946555 612451519 697504054 829460968 303362367 14967005 250810714 164999614 267859557 98687834 331901038 637054868 185529097 48400948 923919143 149253468 528367994 678875310 612544713 613825552 653453269 190350776 347431071 38...

output:

7705

result:

ok 1 number(s): "7705"

Test #23:

score: 0
Accepted
time: 56ms
memory: 24568kb

input:

10000 100000
976525271 192759150 120002943 606091575 335395186 757161820 85210225 663267507 839752375 111342071 137956507 240887746 908844565 942226704 169309769 622850535 916415077 539498152 126155848 746028338 780441576 332328843 280663434 303859356 305461811 334859009 553084839 20315178 259007819...

output:

10099

result:

ok 1 number(s): "10099"

Test #24:

score: 0
Accepted
time: 12ms
memory: 24172kb

input:

10000 9999
406085210 282868337 287131237 127054463 392356693 62787819 834870109 285722192 628138017 131171447 31628498 440784019 550189258 974882404 158349512 464000012 303617766 10433009 328100146 345681501 142604978 723443663 741924030 871093537 18697590 566784538 108893137 878947863 798942228 253...

output:

10030

result:

ok 1 number(s): "10030"

Test #25:

score: -100
Wrong Answer
time: 8ms
memory: 24044kb

input:

10000 9999
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

-15

result:

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