QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #433035 | #5297. 糖果公园 | Le0Chan | 0 | 25ms | 10888kb | C++20 | 2.8kb | 2024-06-07 22:43:59 | 2024-06-07 22:44:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace Le0{
#define LL long long
const int N=1e5+5,B=2000;
int n,m,Q,tot,tot2,df,tp;
LL cnt;
int v[N],w[N],c[N],be[N],ed[N],s[N],st[N][23],dfn[N],t[N];
bool vis[N];
LL ans[N];
vector<int> g[N];
void add(int x,int y){g[x].push_back(y);}
struct node{
int tim,l,r,k;
}q[N];
struct modi{
int x,y;
}a[N];
void dfs(int x,int fa){
st[dfn[x]=++df][0]=fa;
s[++tp]=x;be[x]=tp;
for(int y:g[x]){
if(y!=fa){
dfs(y,x);
}
}
s[++tp]=x;ed[x]=tp;
}
int cp(int x,int y){return dfn[x]<dfn[y]?x:y;}
int lca(int x,int y){
if(x==y) return x;
x=dfn[x],y=dfn[y];
if(x>y) swap(x,y);
x++;int S=__lg(y-x+1);
return cp(st[x][S],st[y-(1<<S)+1][S]);
}
void add(int x){
t[x]++;
cnt+=1ll*v[x]*w[t[x]];
}
void del(int x){
cnt-=1ll*v[x]*w[t[x]];
t[x]--;
}
void work(int x){
if(!vis[x]) add(c[x]);
else del(c[x]);
vis[x]^=1;
}
bool cmp(node a,node b){
if(a.l/B==b.l/B){
if(a.r/B==b.r/B){
return a.tim<b.tim;
}return a.r<b.r;
}return a.l<b.l;
}
int main(){
cin>>n>>m>>Q;
for(int i=1;i<=m;i++) cin>>v[i];
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
add(x,y);add(y,x);
}
dfs(1,0);
for(int j=1;j<=20;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=cp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1,op,x,y;i<=Q;i++){
cin>>op>>x>>y;
if(op==1){
if(be[x]>be[y]) swap(x,y);
int lc=lca(x,y);
if(x==lc) q[++tot]={i,be[x],be[y],0};
else q[++tot]={i,ed[x],be[y],lc};
}
else a[i]={x,y};
}
sort(q+1,q+1+tot,cmp);
int L=1,R=0,ti=0;
for(int i=1;i<=tot;i++){
while(L>q[i].l) work(s[--L]);while(R<q[i].r) work(s[++R]);
while(L<q[i].l) work(s[L++]);while(R>q[i].r) work(s[R--]);
while(ti<q[i].tim){
ti++;
int x=a[ti].x;int &y=a[ti].y;
if(x){
if(vis[x]&&x>=L&&x<=R) del(c[x]);
swap(x,y);
if(vis[x]&&x>=L&&x<=R) add(c[x]);
}
}
while(ti>q[i].tim){
int x=a[ti].x;int &y=a[ti].y;
if(x){
if(vis[x]&&x>=L&&x<=R) del(c[x]);
swap(x,y);
if(vis[x]&&x>=L&&x<=R) add(c[x]);
}
ti--;
}
if(q[i].k) add(c[q[i].k]);
ans[q[i].tim]=cnt;
if(q[i].k) del(c[q[i].k]);
}
for(int i=1;i<=Q;i++){
if(!a[i].x) cout<<ans[i]<<'\n';
}
return 0;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
return Le0::main();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 9792kb
input:
20 20 20 338985 290791 463601 487134 164037 217966 634037 150123 864209 974801 42241 909963 920357 443745 134001 852157 115722 364223 450033 259781 963481 938865 915101 822609 811713 768863 730441 590323 563935 559238 483185 478333 476461 431631 360547 123470 103899 93068 51575 31346 19 11 19 18 19 ...
output:
1692900670227 1924186465420 1788619871315 1156288963796 1366295063442 1534854137430 2622192801123 2610331132351 3221362111222 3180663710301 1513578549988 1366295063442 2000515357202 1720343753731
result:
wrong answer 4th numbers differ - expected: '1428797039393', found: '1156288963796'
Test #2:
score: 0
Wrong Answer
time: 5ms
memory: 7952kb
input:
1994 405 1995 556641 923161 368121 885153 370001 753533 356267 140326 312301 783041 203028 233351 298226 63313 481496 767119 609731 83601 244285 123019 322557 89764 320795 510500 597803 130811 616297 926775 53285 223840 767926 528855 663829 93371 7616 504897 555458 588585 439361 321306 318738 292666...
output:
230433123140444 215718604200716 143518142036549 42573577873741 106629622734197 177630359398374 101699039188090 68443719001360 90305413601598 144592558660551 38630760979662 129711069453009 102229623916747 205740149226050 102803081442787 136132201123398 43082085649858 70976833077423 52811675830936 216...
result:
wrong answer 1st numbers differ - expected: '238065394611882', found: '230433123140444'
Test #3:
score: 0
Wrong Answer
time: 25ms
memory: 10888kb
input:
9999 7777 8888 350689 340640 742515 847983 603105 291777 123546 793423 123828 81197 689725 179719 163877 82548 81941 315278 837007 706985 328661 54846 70061 844381 44818 920226 401209 383073 958769 885881 704561 623241 296481 865665 638927 35204 446821 733545 906869 461290 504161 780939 437893 78051...
output:
921169644418049 1013393547321595 1870574472350797 591287329294163 1871952543115436 1346396956272717 1259781915564874 1115237221216804 986959548836181 901980025519098 1384007638844346 1307225720284204 732698576584825 791541162813297 1518059226196970 1027576814440423 301702416832737 636432999591817 16...
result:
wrong answer 1st numbers differ - expected: '917941805267440', found: '921169644418049'
Test #4:
score: 0
Runtime Error
input:
80000 100 79999 636177 829001 946691 381143 658421 84345 812823 285627 753201 780625 199608 200621 758328 43837 174785 860657 837685 121124 628536 250361 57056 763835 854851 569459 704553 381031 452536 11521 83241 118985 952062 804495 957289 395051 600601 199598 983966 501357 608555 75049 620761 808...
output:
result:
Test #5:
score: 0
Runtime Error
input:
90000 100 89999 910319 741245 15001 621563 607827 958814 713422 778999 4129 398965 560121 469526 583062 793795 750877 765421 654537 761001 585305 45111 299016 489428 871086 858817 286721 387466 267822 198069 844341 963241 515351 85267 657201 1676 719041 823049 685279 461279 316045 966515 837671 6194...
output:
result:
Test #6:
score: 0
Runtime Error
input:
77654 77600 78888 533241 917289 57915 11289 2116 27801 173446 367131 419217 781673 361526 442749 297129 775770 364138 523309 514521 483929 126657 426121 771921 846145 557801 368163 244436 901113 851505 582225 570386 407457 32071 958501 286399 163034 982921 45093 169525 152381 529601 317785 363958 43...
output:
result:
Test #7:
score: 0
Runtime Error
input:
87654 87654 88888 11969 827905 718296 546441 34643 409376 899435 13745 273000 219440 121415 258869 607041 915541 54841 170243 312971 52666 551629 136173 199369 595404 804731 152679 911401 592177 652725 693627 612183 122796 697911 745150 951821 79862 490878 861269 683115 752401 96321 711061 79146 682...
output:
result:
Test #8:
score: 0
Runtime Error
input:
75757 80000 79797 484017 923271 503479 371693 407131 675651 128065 559955 230433 640753 664171 725701 411881 203961 604521 391313 135601 753991 596483 186409 795188 808589 915505 468366 796905 385309 144431 27036 750997 276351 306785 246681 417281 890361 604385 728641 183905 396657 608665 297185 965...
output:
result:
Test #9:
score: 0
Runtime Error
input:
85757 80000 89797 365071 866171 292001 203861 238608 342899 587741 829194 525736 476155 202388 341423 792260 152351 302911 498503 901389 69215 401983 799291 430211 108169 60713 908033 328701 585128 628465 666585 238471 886049 462521 9774 928664 402969 934216 458465 105337 302193 419801 55383 20031 7...
output:
result:
Test #10:
score: 0
Runtime Error
input:
100000 100000 100000 830821 840887 527523 351839 415371 428013 117556 863473 387567 587411 883157 808805 956353 745921 952210 610807 502909 398921 659296 997417 610551 598717 567276 427661 755457 546291 617737 698135 997273 438737 935176 220641 697316 562857 850451 306042 323721 900500 653557 949002...