QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #102260 | #2580. 语言 | chengzk | 0 | 1109ms | 156244kb | C++14 | 2.8kb | 2023-05-02 19:50:20 | 2023-05-02 19:50:23 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define mid (l+r)/2
using namespace std;
const int N=2e5+5;
int n,m,aaa,bbb,xx,yy,zz,ll,rr,rt[N],ks[N],js[N];
long long ans,ans1;
vector<int>G[N];
struct TDS{
int tp[N],zs[N],siz[N],dep[N],fa[N][22],cnt,Lca;
int tot,s[N*80],gs[N*80],ls[N*80],rs[N*80];
void up(int roo,int l,int r){gs[roo]=(s[roo]>0)?(r-l+1):(gs[ls[roo]]+gs[rs[roo]]);return ;}
void work(int roo,int ad){s[roo]+=ad;return ;}
void upd(int &roo,int l,int r,int sel,int ser,int ad){
if (r<sel||ser<l) return ;if (!roo) roo=++tot;
if (sel<=l&&r<=ser) {work(roo,ad);up(roo,l,r);return ;}
upd(ls[roo],l,mid,sel,ser,ad);upd(rs[roo],mid+1,r,sel,ser,ad);up(roo,l,r);
}
int merge(int ro1,int ro2,int l,int r){
if (!ro1||!ro2) return ro1+ro2;
s[ro1]+=s[ro2];up(ro1,l,r);if (l==r) return ro1;
ls[ro1]=merge(ls[ro1],ls[ro2],l,mid);rs[ro1]=merge(rs[ro1],rs[ro2],mid+1,r);
up(ro1,l,r);return ro1;
}
void dfs(int x,int fath){
zs[x]=0;siz[x]=1;dep[x]=dep[fath]+1;fa[x][0]=fath;
for (int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for (int i=0,u;i<G[x].size();i++) if ((u=G[x][i])!=fath)
dfs(u,x),zs[x]=(siz[zs[x]]<siz[u])?u:zs[x];
}
void dfs1(int x,int fath,int top){
ks[x]=++cnt;tp[x]=top;if (zs[x]){dfs1(zs[x],x,top);}
for (int i=0,u;i<G[x].size();i++) if ((u=G[x][i])!=fath&&zs[x]!=u) dfs1(u,x,u);
js[x]=cnt;
}
int findLca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
for (int i=20;i>=0;i--) if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if (x==y) return x;
for (int i=20;i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void add(int roo,int l,int r,int ad){upd(rt[roo],1,n,l,r,ad);return ;}
void Ins(int x,int y){
Lca=findLca(x,y);xx=x,yy=y;zz=fa[Lca][0];
// cout<<xx<<" "<<yy<<" "<<zz<<" "<<Lca<<"__";
while (tp[x]!=tp[y]){
if (dep[x]<dep[y]) swap(x,y);ll=ks[tp[x]];rr=ks[x];
// cout<<tp[x]<<" "<<x<<" "<<ll<<" "<<rr<<"__";
add(xx,ll,rr,1);add(yy,ll,rr,1);add(Lca,ll,rr,-1);add(zz,ll,rr,-1);
x=fa[tp[x]][0];
}
if (dep[x]<dep[y]) swap(x,y);ll=ks[y];rr=ks[x];
// cout<<y<<" "<<x<<" "<<ll<<" "<<rr<<"_"<<endl;
add(xx,ll,rr,1);add(yy,ll,rr,1);add(Lca,ll,rr,-1);add(zz,ll,rr,-1);
return ;
}
void solve(int x,int fath){
for (int i=0,u;i<G[x].size();i++) if ((u=G[x][i])!=fath)
solve(u,x),rt[x]=merge(rt[x],rt[u],1,n);
ans1=gs[rt[x]];ans+=max(ans1-1,0ll);
cout<<x<<" "<<ks[x]<<" "<<rt[x]<<":"<<ans1<<"__**__"<<endl;
}
}Tds;
void Insert(int x,int y){G[x].push_back(y),G[y].push_back(x);}
int main()
{
cin>>n>>m;
for (int i=1;i<n;i++) scanf("%d%d",&aaa,&bbb),Insert(aaa,bbb);
Tds.dfs(1,0);Tds.dfs1(1,0,1);
for (int i=1;i<=m;i++) scanf("%d%d",&aaa,&bbb),Tds.Ins(aaa,bbb);
Tds.solve(1,0);
printf("%lld\n",ans/2ll);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 8684kb
input:
297 297 281 46 39 260 193 121 50 162 18 15 43 104 154 293 131 121 70 112 247 121 17 59 240 102 277 185 90 121 134 38 46 116 27 127 97 7 33 49 24 297 31 286 12 18 57 121 133 150 183 286 186 194 153 121 117 189 256 121 266 192 106 230 80 249 164 73 211 197 264 4 53 47 203 43 286 69 221 146 214 167 142...
output:
193 31 0:0__**__ 131 32 0:0__**__ 247 33 0:0__**__ 90 34 0:0__**__ 57 35 0:0__**__ 153 36 3869:85__**__ 256 37 12000:52__**__ 181 38 11254:78__**__ 56 39 14552:79__**__ 136 115 1994:84__**__ 147 116 6614:91__**__ 244 114 1163:104__**__ 16 118 8471:88__**__ 91 119 1984:97__**__ 263 117 3722:110__**__...
result:
wrong answer 1st lines differ - expected: '15910', found: '193 31 0:0__**__'
Test #2:
score: 0
Wrong Answer
time: 2ms
memory: 8664kb
input:
293 296 286 83 144 202 108 42 70 112 85 29 291 112 14 112 97 292 123 168 247 112 143 112 238 102 174 262 252 185 63 112 137 103 64 112 15 11 282 273 248 1 100 112 159 181 226 20 47 129 258 34 72 160 189 282 50 252 145 175 13 112 250 152 106 267 30 196 22 112 43 104 17 112 105 80 95 177 34 251 259 29...
output:
155 104 157:115__**__ 96 105 8476:110__**__ 166 103 4370:125__**__ 182 107 1827:112__**__ 255 108 4048:119__**__ 293 106 7082:124__**__ 126 102 6773:143__**__ 46 111 1:125__**__ 68 112 1943:113__**__ 217 110 4165:144__**__ 173 115 5820:114__**__ 56 116 6296:5__**__ 123 114 5820:116__**__ 245 118 224...
result:
wrong answer 1st lines differ - expected: '15234', found: '155 104 157:115__**__'
Test #3:
score: 0
Wrong Answer
time: 60ms
memory: 18676kb
input:
4858 4888 3140 3181 1664 1770 4200 493 3671 59 3209 1842 2502 2173 681 2155 2654 3278 4174 2554 3282 587 3337 4086 4287 2326 779 3708 2048 2448 3634 3148 4214 59 2083 59 325 1216 351 878 1497 3495 4642 4242 115 4419 1588 2172 1054 4610 3007 59 4821 2816 2078 1195 782 2610 2559 3187 4576 292 4000 59 ...
output:
3671 507 191874:1126__**__ 4214 508 0:0__**__ 2083 509 305440:1132__**__ 3007 510 572014:1126__**__ 4000 511 0:0__**__ 477 512 386792:1127__**__ 77 513 339999:268__**__ 4079 514 354052:1112__**__ 972 515 121494:1126__**__ 1642 516 353064:1608__**__ 1830 517 210001:4__**__ 1666 518 57464:1132__**__ 1...
result:
wrong answer 1st lines differ - expected: '3627298', found: '3671 507 191874:1126__**__'
Test #4:
score: 0
Wrong Answer
time: 72ms
memory: 18420kb
input:
4983 4867 1535 1610 1899 1266 3238 2426 2405 1420 2578 4364 300 2296 4590 254 396 1242 3129 3631 324 3583 3748 1155 2771 1200 4246 4603 2331 1110 2824 1891 2544 1237 3487 3040 3687 2834 109 4636 4687 1200 1649 2420 2008 2926 2516 4852 3440 1551 765 3096 2754 1200 4879 4820 3073 4787 91 1200 2911 257...
output:
2771 330 0:0__**__ 4687 331 52385:1351__**__ 2754 332 0:0__**__ 91 333 0:0__**__ 3825 334 311174:1352__**__ 3380 335 0:0__**__ 3133 336 87966:1396__**__ 2371 337 202568:1345__**__ 3463 338 99158:1343__**__ 4223 339 365522:1343__**__ 19 340 0:0__**__ 4340 341 258157:498__**__ 1191 342 0:0__**__ 4159 ...
result:
wrong answer 1st lines differ - expected: '3873876', found: '2771 330 0:0__**__'
Test #5:
score: 0
Wrong Answer
time: 1044ms
memory: 156100kb
input:
96808 99508 40695 40696 73595 73596 13615 13616 65545 65546 19391 19392 2353 2354 26730 26731 42541 42542 28008 28009 96282 96283 76530 76531 5872 5873 61286 61287 56072 56073 87216 87217 38177 38178 50372 50373 329 330 58557 58558 43629 43630 77425 77426 8017 8018 43507 43508 35913 35914 31123 3112...
output:
96808 96808 913323:5964__**__ 96807 96807 288044:5964__**__ 96806 96806 810075:7720__**__ 96805 96805 102080:7720__**__ 96804 96804 83195:8293__**__ 96803 96803 288062:8293__**__ 96802 96802 839134:8293__**__ 96801 96801 2914224:8293__**__ 96800 96800 3646618:8293__**__ 96799 96799 4376850:8293__**_...
result:
wrong answer 1st lines differ - expected: '907477207', found: '96808 96808 913323:5964__**__'
Test #6:
score: 0
Wrong Answer
time: 1109ms
memory: 156244kb
input:
97092 99840 40695 40696 73595 73596 13615 13616 65545 65546 19391 19392 2353 2354 26730 26731 42541 42542 28008 28009 96282 96283 76530 76531 5872 5873 61286 61287 56072 56073 87216 87217 38177 38178 50372 50373 329 330 58557 58558 43629 43630 77425 77426 8017 8018 43507 43508 35913 35914 31123 3112...
output:
97092 97092 777356:8185__**__ 97091 97091 412941:9167__**__ 97090 97090 148905:9167__**__ 97089 97089 332408:9167__**__ 97088 97088 112453:9167__**__ 97087 97087 1844444:9167__**__ 97086 97086 295348:9167__**__ 97085 97085 295331:9167__**__ 97084 97084 295365:9167__**__ 97083 97083 1369119:9167__**_...
result:
wrong answer 1st lines differ - expected: '910321604', found: '97092 97092 777356:8185__**__'
Test #7:
score: 0
Runtime Error
input:
99924 97275 24723 56564 44193 73644 54591 22570 56965 55653 91120 48245 25702 41871 77524 67327 80722 7653 87907 54339 86418 76838 41215 78202 48534 59032 44710 32114 38879 34955 17434 99405 37456 39328 66649 35177 76911 54339 40612 7834 70065 54339 29689 38076 48485 60166 50641 57751 97629 94661 47...
output:
result:
Test #8:
score: 0
Runtime Error
input:
99498 96777 19744 18289 4605 93580 43036 31212 42702 45122 16545 73127 70905 51611 27911 61773 48069 83562 95567 11283 66495 45122 65856 15502 26003 58273 46733 45122 7043 7247 80433 55125 67878 88881 20197 45122 39212 80482 25962 45122 62830 45122 40173 39170 14714 82850 24093 66693 50604 61001 866...
output:
result:
Test #9:
score: 0
Runtime Error
input:
99214 98195 8234 36494 37451 75094 31731 33067 19984 36494 52041 11042 4970 37696 26871 43916 87010 25881 37092 8701 75030 89583 4706 75209 24536 4378 37412 69085 88883 17123 79895 36494 95090 79450 95892 73714 61952 77454 81044 8337 68757 11047 73613 36494 60137 16120 41322 47605 49142 24141 79221 ...
output:
result:
Test #10:
score: 0
Runtime Error
input:
98930 97863 31939 63734 42943 69741 55957 86464 76683 63177 19844 89880 92738 35520 42184 7020 98581 89880 73665 19084 91904 89880 32101 31332 16923 89880 64777 72859 39842 59094 18714 87378 5513 21706 54019 89880 16688 80816 1260 35635 83182 52628 32044 61306 26440 39530 77024 69004 20199 64299 434...