QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#449463 | #5358. 宝石游戏 | Rikku_eq | 15 | 1643ms | 25980kb | C++14 | 3.4kb | 2024-06-21 10:56:35 | 2024-06-21 10:56:36 |
Judging History
answer
#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int n, m, c[N];
int dep[N], len[N], son[N], tI[N], tO[N], tmr;
vector <int> to[N];
ll buf[N*2], buf2[N*2], *f[N], *suf[N], *cur=buf, *cur2=buf2;
ll tg[N];
int B, st[N], idB[N];
ll ans[N];
vector <int> vec[N];
struct Qry { int op, x, v; } q[N];
void dfs_son (int u, int fa)
{
for (int i=0; i<(int)to[u].size(); i++) {
int v=to[u][i];
if (v==fa) { continue; }
dfs_son(v, u);
if (len[v]>len[son[u]]) { son[u]=v; }
}
len[u]=len[son[u]]+1;
}
void dfs_f (int u, int fa)
{
tI[u]=++tmr; dep[u]=dep[fa]+1;
if (son[u]) {
f[son[u]]=f[u]+1;
suf[son[u]]=suf[u]+1;
dfs_f(son[u], u);
}
for (int i=0; i<(int)to[u].size(); i++) {
int v=to[u][i];
if (v==fa || v==son[u]) { continue; }
f[v]=cur; cur+=(len[v]+1);
suf[v]=cur2; cur2+=(len[v]+1);
dfs_f(v, u);
}
tO[u]=tmr;
}
bool up (int u, int v) { return tI[u]<=tI[v] && tO[v]<=tO[u]; }
void cal (int u, int fa, int idb)
{
if (son[u]) {
cal(son[u], u, idb);
}
f[u][0]=c[u];
suf[u][0]=(len[u]==0 ? f[u][0] : (suf[u][1]^f[u][0]));
for (int i=0; i<(int)to[u].size(); i++) {
int v=to[u][i];
if (v==fa || v==son[u]) { continue; }
cal(v, u, idb);
for (int j=0; j<=len[v]+2; j++) { tg[j]=0; }
for (int j=0; j<=len[v]; j++) {
tg[j+1]=(f[u][j+1]^(f[u][j+1]+f[v][j]));
f[u][j+1]+=f[v][j];
}
tg[0]=0;
for (int j=len[v]+1; j>=0; j--) {
if (j<=len[v]) { tg[j]^=tg[j+1]; }
suf[u][j]^=tg[j];
}
}
for (int i=0; i<(int)vec[u].size(); i++) {
int qid=vec[u][i], L=q[qid].v;
if (L>=len[u]) { ans[qid]=suf[u][0]; }
else { ans[qid]=(suf[u][0]^suf[u][L+1]); }
for (int j=st[idb]; j<qid; j++) {
if (q[j].op==2) { continue; }
int x=q[j].x, v=q[j].v;
if (up(u, x) && dep[x]-dep[u]<=L) {
ans[qid]^=(f[u][dep[x]-dep[u]]^(f[u][dep[x]-dep[u]]-c[x]+v));
}
}
}
}
void solve ()
{
len[0]=-1; dfs_son(1, 0);
f[1]=cur; cur+=(len[1]+1);
suf[1]=cur2; cur2+=(len[1]+1);
dfs_f(1, 0);
for (int i=1; i<=m; i=st[idB[i]+1]) {
for (int u=1; u<=n; u++) { vec[u].clear(); }
fill(buf, cur, 0);
fill(buf2, cur2, 0);
for (int j=i; j<st[idB[i]+1]; j++) {
if (q[j].op==2) { vec[q[j].x].push_back(j); }
}
cal(1, 0, idB[i]);
for (int j=i; j<st[idB[i]+1]; j++) {
if (q[j].op==1) { c[q[j].x]=q[j].v; }
}
}
for (int i=1; i<=m; i++) if (q[i].op==2) { printf("%lld\n", ans[i]); }
}
int main ()
{
// freopen("0test.in", "r", stdin);
// freopen("0test.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i=1; i<=n; i++) { scanf("%d", &c[i]); }
for (int i=1; i<n; i++) {
int u, v; scanf("%d %d", &u, &v);
to[u].push_back(v);
to[v].push_back(u);
}
for (int t=1; t<=m; t++) {
scanf("%d %d %d", &q[t].op, &q[t].x, &q[t].v);
}
B=ceil(sqrt(m));
for (int i=1; i<=m; i++) {
idB[i]=((i-1)/B)+1;
if (!st[idB[i]]) { st[idB[i]]=i; }
}
st[idB[m]+1]=m+1;
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 0ms
memory: 18280kb
input:
7 5 1 2 3 4 5 6 7 3 1 2 4 3 7 6 7 5 4 4 1 2 1 1 2 4 0 2 7 2 1 6 0 2 7 1
output:
6 4 1 7
result:
ok 4 lines
Test #2:
score: -7
Wrong Answer
time: 2ms
memory: 18208kb
input:
1000 1000 168301431 651266519 181230331 997564131 922958564 240686472 828844423 997226083 101127334 549182223 815802272 962217487 872007143 308493550 875871642 388491137 726655288 632336322 36483715 91926885 973887125 969715766 903583959 709995095 551483747 454472802 645719871 210282402 246763026 76...
output:
13348898220 15233413294 1022133674 9805924300 1260198611 3788645358 14159961177 14583954163 13158452364 16810205245 2373615391 14513880545 14300884783 14042178314 14648556653 14592588744 13160234103 13907249441 13749193468 2587887866 13650585034 13022756757 15360008256 11290079854 15420423634 426162...
result:
wrong answer 11th lines differ - expected: '2300315550', found: '2373615391'
Subtask #2:
score: 0
Wrong Answer
Test #14:
score: 13
Accepted
time: 1542ms
memory: 25980kb
input:
100000 100000 405003099 610837546 348589233 875137317 862931320 731758484 582603782 989991623 184749683 961137536 740146957 148627391 849777698 445045421 119699522 266347287 445197848 974544475 91680144 328247730 665144499 422991113 252383902 770011580 393442268 470439648 712319066 315986988 4789186...
output:
981730896 747543671 48940353 1063131294 1664022464 2108439828 1676415478 1758820567 841425155 1487919939 550289640 502601409 857432062 545225207 534191912 1529755415 1934872270 184068092 530775075 2435829606 1639080466 1086525690 4252299227 862471314 806170012 960496538 1470813685 517621825 38523298...
result:
ok 75043 lines
Test #15:
score: 0
Accepted
time: 1532ms
memory: 25760kb
input:
100000 100000 22451398 673148902 34052819 342197803 764092498 25380768 945504884 17947222 525466824 754276942 188383557 882731403 257464604 662583754 367373408 712066583 679220139 887137605 739209552 575564762 843930549 263510226 225951309 245149866 250834537 591353233 650464089 675881261 494412011 ...
output:
82249782 903608581 848979643 1352033746 1105535098 2071118381 1247772197 1729442137 555339550 389188883 925646753 90336849 2020258191 1058937661 263809303 674479575 3493369318 249463195 2072321036 3096285967 412904450 499991032 3098452671 292926402 109104959 609796851 1533158319 1969354357 429846460...
result:
ok 50050 lines
Test #16:
score: 0
Accepted
time: 1555ms
memory: 25736kb
input:
100000 100000 604879379 483937913 832246812 761377727 37350489 529218728 768379889 881234233 214027555 831562029 755516063 377543211 693053827 719265606 53470761 544321536 540487467 158899081 642992618 997934233 608199008 434689783 79837133 950172500 239836431 672608924 651470781 827008467 837359094...
output:
276667027 5231855036 950049566 1463503948 854203396 1614605468 762091418 408526838 109052637 2169632019 261284886 887669737 1394086616 692829809 804469661 166519588 828729769 541569039 1318267764 508724942 265487119 103626187 1713786134 35075789 860838639 326898130 434864182 780624667 3422658139 240...
result:
ok 25212 lines
Test #17:
score: -13
Wrong Answer
time: 1521ms
memory: 25608kb
input:
100000 100000 90033493 506197929 654158695 385575693 670749030 108284461 792545276 31913719 661245488 345850838 5781374 206979645 90527744 98792190 890863477 323771780 730710998 203628158 5753938 551018780 538537077 304323176 43800336 277050891 194148772 548837868 717507235 498320188 536772516 80467...
output:
44134520 752277245 1044402745 915396616 903671986 464003602 62822110 595446551 36304461 507312244 1090602067 396260862 622059563 722616932 3777684567 606756169 579472931 2439987728 1068217409 145908799 2099683612 563391690 1346461069 1472335526 1580506615 1386616783 471669685 731881153 1023453055 41...
result:
wrong answer 790th lines differ - expected: '3621241302', found: '4694434262'
Subtask #3:
score: 0
Wrong Answer
Test #20:
score: 0
Wrong Answer
time: 1643ms
memory: 24736kb
input:
100000 100000 391636738 188947351 607003168 699971181 102753269 291890533 830830147 76057458 623517854 58958317 449828617 773557323 669394342 548355126 601286710 238603435 809091745 772998770 894693501 564199529 196062134 2803096 781469712 870912328 138245421 273392139 476952377 787775209 401014779 ...
output:
4014146821 2718560828 1298976569 559452402 3944231402 7231839253 4217065363 7183934527 3576782824 121213840 2168405789 1445110982 1732950814 4104773741 8208349899 4138140954 1976870585 1327869233 1208369754 232829949 2901562179 2506234011 2899215326 296851124 1177782314 3500638395 1397814715 1901081...
result:
wrong answer 637th lines differ - expected: '1450556716', found: '1779774356'
Subtask #4:
score: 15
Accepted
Test #26:
score: 15
Accepted
time: 1561ms
memory: 25796kb
input:
100000 100000 620733757 384382313 514191349 902009280 482178057 905939364 286556695 762555921 287205978 88334200 437152915 320217018 981790168 254780145 881516456 779810222 814317342 292303220 272120273 65511383 98150102 177581894 12582058 656218139 789187030 442791738 134622788 62465827 954191430 1...
output:
11993349061 8780326633 12098734542 3054518456 11132272208 9585682103 11426273049 9266587001 9296220252 8746673304 4802112670 10135027741 16011873190 16475904355 14930922801 11839935145 11426767823 9934836159 12604090555 9528086705 12243172857 8772822837 10040253862 12634310244 15147379067 1242158338...
result:
ok 100000 lines
Test #27:
score: 0
Accepted
time: 1534ms
memory: 25968kb
input:
100000 100000 883511342 564049614 941195414 598900668 915829631 829831015 643407074 891126166 92067245 365887142 702332684 145270502 515205039 671235251 936256742 475228958 402074099 957052127 879126510 626664803 159325985 184222850 585239338 328661818 152240094 534589476 257519191 151130382 3779217...
output:
2063630803 4179200153 2412722795 6185739950 2998353608 13394484754 3879185083 13724084594 7944210978 4772495240 3405578985 3788694219 766409501 4179447725 6531746521 3796324892 3401077732 4030732251 3140323205 7234147373 2841193851 9134297712 4178369683 5375760737 1728292597 16009739305 6374267178 3...
result:
ok 100000 lines
Test #28:
score: 0
Accepted
time: 1539ms
memory: 25976kb
input:
100000 100000 630739088 854727545 213997617 942616106 924686209 112612965 285117524 980718591 420102739 924177279 200678610 108453610 851012491 955508643 454607030 894576431 970857677 90629694 926468070 149287580 396947181 157250681 247080001 862145714 320691932 610985104 909856197 490164949 4199260...
output:
2245414712 13784514747 14990654935 15992815757 12589139793 3852502945 14744972273 14504205489 15957561316 13078894348 13350873638 16591798222 966172903 15190440053 902570755 15678516642 13328506232 8664101095 14005624638 13405905116 7452625175 4896020820 1001880264 10360008701 11086768300 1489539102...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 1542ms
memory: 25812kb
input:
100000 100000 191250231 309219580 690731263 399929991 435593274 798755180 167069881 258372773 918841503 713152435 988260606 287371534 622270702 123441668 783061281 935580705 651966342 169506624 401246646 921218153 246438741 659216599 630274760 451895519 956125853 390000650 764229955 612330124 636173...
output:
9617457277 6923404079 8183085296 7197029291 7325949990 5084048795 6545284283 6674253656 14765811680 8171584990 2744631007 11230072776 8328615508 8280664219 10036243548 8017128983 11617588398 5934811208 973135573 2782685016 1010587262 13080457267 11409146453 252989735 6791262653 531856512 1065509807 ...
result:
ok 100000 lines
Test #30:
score: 0
Accepted
time: 1569ms
memory: 25964kb
input:
100000 100000 7762290 819228666 308794447 99231206 278021851 291194054 413315059 360495048 714316736 297347475 967091400 457868714 787245716 86819682 859979941 790849084 961215926 116370387 518647008 424424541 712192878 775842450 854304580 125723337 752821089 960128888 659290076 897894732 493935911 ...
output:
1944698551 1186025353 1555116504 3328994813 15227617740 7560248382 3641093253 11894697 2313019358 480667145 10760853354 15309532102 2668936316 3237556150 603987652 9830072614 4397497509 4315557576 1524570847 408571158 13487586434 4841759020 2063251252 13483701037 7702057999 8486793595 819859839 1344...
result:
ok 100000 lines
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%