QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#371682 | #4891. 树上的孤独 | zsq147258369 | 30 | 1523ms | 225960kb | C++17 | 3.2kb | 2024-03-30 14:56:30 | 2024-03-30 14:56:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+50,Q=2e6,M=21,inf=1e9+7,T=1e7;
int n,m,q,c[M],val[N];
vector<int>s[M],g[N];
struct edge
{
int u,v,nxt;
}e[N];
int head[N],cnt,dp[M];
void add()
{
int u,v;cin>>u>>v;
e[++cnt]=(edge){u,v,head[u]};head[u]=cnt;
e[++cnt]=(edge){v,u,head[v]};head[v]=cnt;
}
void Aadd()
{
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
void init(int x,int fa)
{
s[x].push_back(x);dp[x]=dp[fa]+1;
for(auto v:g[x])if(v!=fa)
{
init(v,x);
for(auto t:s[v])s[x].push_back(t);
}
}
vector<int>ask[N];
int cc[N],ty[Q],d1[Q],d2[Q],p1[Q],p2[Q],siz[N],son[N],d[N];
void dfs(int x,int f)
{
siz[x]=1;d[x]=d[f]+1;
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==f)continue;
dfs(v,x);siz[x]+=siz[v];
if(siz[v]>siz[son[x]])son[x]=v;
}
}
vector<int>p[M];
int mindep[M][N],vis[M][N];
int sum[T],tot,tl[T],tr[T],ro[N];
#define mid ((l+r)>>1)
void insert(int&x,int l,int r,int d,int w)
{
++tot;sum[tot]=sum[x]+w;tl[tot]=tl[x];tr[tot]=tr[x];x=tot;
if(l==r)return;
if(d<=mid)insert(tl[x],l,mid,d,w);else insert(tr[x],mid+1,r,d,w);
}
int find(int x,int l,int r,int L,int R)
{
if(L<=l&&R>=r)return sum[x];
if(!x)return 0;
int ans=0;
if(L<=mid)ans+=find(tl[x],l,mid,L,R);
if(R>mid)ans+=find(tr[x],mid+1,r,L,R);
return ans;
}
void up(int dep,int w,int d,int x)
{
if(!vis[dep][w])
{
vis[dep][w]=1;
mindep[dep][w]=d;
insert(ro[x],1,m,d,1);
p[dep].push_back(w);
}
else if(mindep[dep][w]>d)
{
insert(ro[x],1,m,mindep[dep][w],-1);
insert(ro[x],1,m,d,1);
mindep[dep][w]=d;
}
}
void merge(int u,int v,int x)
{
for(auto w:p[v])up(u,w,mindep[v][w],x),vis[v][w]=0;
}
void solve(int x,int fa,int dep)
{
if(son[x])solve(son[x],x,dep),ro[x]=ro[son[x]];
up(dep,val[x],d[x],x);
for(int i=head[x];i;i=e[i].nxt)
{
int v=e[i].v;if(v==fa||v==son[x])continue;
p[dep+1].clear();
solve(v,x,dep+1);merge(dep,dep+1,x);
}
for(auto&t:ask[x])t=(vis[dep][t]?mindep[dep][t]:inf);
}
int mx=0;
main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<n;i++)Aadd();
for(int i=1;i<m;i++)add();
for(int i=1;i<=n;i++)
{
cin>>c[i];mx=max(mx,c[i]);
}
for(int i=1;i<=m;i++)
{
cin>>val[i];mx=max(mx,val[i]);
}
init(1,0);
for(int i=1,u,v;i<=q;i++)
{
cin>>ty[i];
if(ty[i]==1)
{
cin>>p1[i]>>p2[i]>>d1[i]>>d2[i];
for(auto x:s[p1[i]])ask[p2[i]].push_back(c[x]);
}
else cin>>u>>v,c[u]=v,mx=max(mx,v);
}
dfs(1,1);solve(1,1,1);
for(int i=1,las=0;i<=q;i++)if(ty[i]==1)
{
d1[i]^=las;d2[i]^=las;
las=find(ro[p2[i]],1,m,d[p2[i]],min(m,d[p2[i]]+d2[i]));
for(auto x:s[p1[i]])
{
if(dp[x]-dp[p1[i]]<=d1[i])las+=(ask[p2[i]][cc[p2[i]]]>d[p2[i]]+d2[i]);
++cc[p2[i]];
}
cout<<las<<'\n';
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 28072kb
input:
20 2000 2000 8 15 8 13 14 8 14 7 12 14 12 1 9 13 9 4 5 9 5 10 2 5 2 19 6 19 6 16 11 7 11 20 18 2 18 17 3 6 1395 1783 1395 1735 1735 457 457 739 739 438 438 101 101 441 441 1879 1879 1238 1238 501 501 1732 1732 1910 1910 2000 2000 834 834 917 917 111 111 780 780 1966 1966 1604 1604 623 623 1748 1748 ...
output:
105 93 2 45 19 55 192 26 69 21 22 200 79 89 137 33 68 69 55 37 24 8 24 79 59 100 27 200 40 74 97 21 87 37 197 76 28 49 11 20 55 62 24 5 109 158 25 23 15 102 38 109 28 76 172 83 31 147 145 9 136 33 109 142 120 69 35 67 20 47 59 51 56 14 35 154 111 130 144 200 21 81 83 40 73 25 30 39 163 53 62 51 97 2...
result:
wrong answer 4th numbers differ - expected: '44', found: '45'
Subtask #2:
score: 20
Accepted
Test #3:
score: 20
Accepted
time: 980ms
memory: 181440kb
input:
20 200000 500000 8 18 8 4 2 4 2 14 13 4 13 16 6 4 6 3 1 4 1 17 15 6 15 19 7 17 7 11 5 14 5 10 20 7 12 15 9 8 165302 77239 165302 198189 165302 180850 165302 192738 165302 173589 165302 194087 165302 191990 165302 167370 165302 101092 165302 92553 165302 163654 165302 122381 165302 152105 165302 1919...
output:
2 17595 3898 3423 16 518 5138 11355 21 7340 21 18327 15797 6638 514 1184 6110 1884 6241 662 16738 13230 1597 5446 6074 2387 6265 2 21 282 3511 1806 1236 1038 17804 4657 5536 4633 4547 21 244 2703 2 4610 8571 4037 21 13498 5648 2054 3489 4869 5828 802 2072 1482 13232 2593 938 16769 2 17623 353 5 21 7...
result:
ok 500000 numbers
Test #4:
score: 0
Accepted
time: 939ms
memory: 187944kb
input:
20 200000 500000 11 2 11 1 17 1 17 6 10 2 10 16 20 6 20 15 12 1 12 4 9 16 9 3 7 1 13 15 8 15 8 5 18 7 18 14 19 12 146231 199607 146231 196481 196481 194263 194263 192044 192044 169873 169873 141903 141903 129271 129271 176167 176167 170198 170198 173775 173775 174130 174130 184691 184691 198900 1989...
output:
933 12179 2009 2889 5129 7229 2884 5588 1070 21 2789 2194 654 2643 7840 3203 3946 105 1626 4635 775 2 14 6001 18249 18326 2 1386 3505 11361 1254 4501 5630 21 12011 1392 2902 5252 7857 4 1038 1796 3342 129 19959 18597 1924 116 104 1603 3593 4365 3967 921 1007 2344 4728 3051 2048 4607 4563 1648 8059 3...
result:
ok 500000 numbers
Test #5:
score: 0
Accepted
time: 963ms
memory: 187648kb
input:
20 200000 500000 11 19 11 12 6 12 6 8 20 19 20 7 1 6 1 2 9 11 9 10 15 6 15 17 3 7 3 14 13 19 4 13 4 18 5 6 5 16 164001 91176 164001 174000 174000 170154 170154 69790 69790 174420 174420 193462 193462 149823 149823 188081 188081 127489 127489 191901 191901 194376 194376 197936 197936 185448 185448 19...
output:
5329 19807 5406 4355 2 1453 3216 21 2758 2561 387 8122 6615 4577 6108 2 2224 586 2950 19824 3119 6437 4852 5552 17244 7466 5462 2909 9992 19918 6653 19811 448 1026 1467 424 21 3056 1866 4262 9943 6499 3180 3688 6479 5096 6369 21 232 1765 2369 1789 1942 1141 3690 8680 7346 5265 21 16599 701 4354 1413...
result:
ok 500000 numbers
Test #6:
score: 0
Accepted
time: 994ms
memory: 198672kb
input:
20 200000 500000 17 5 17 11 18 5 18 14 1 17 1 3 16 18 16 13 7 16 7 15 9 15 9 4 12 11 12 2 20 14 20 19 8 9 8 10 6 17 166750 113956 166750 160259 160259 143147 143147 172478 172478 173006 173006 89817 89817 196218 196218 191942 191942 193748 193748 177077 177077 157435 157435 125058 125058 164374 1643...
output:
2490 7164 1575 19999 2452 1702 26 21 5118 19981 10942 21 21 19266 1523 13 21 6341 21 1040 581 1643 7021 16863 7376 1626 1211 1982 21 15029 10542 14571 135 21 1001 21 1390 4982 2928 1539 5422 1095 2923 4872 1377 19997 14571 7196 4640 1988 1707 5216 5742 17354 12204 1941 17445 516 21 13 14682 19992 21...
result:
ok 500000 numbers
Subtask #3:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 208ms
memory: 91380kb
input:
20 100000 100000 16 12 16 20 6 12 6 18 2 16 2 8 5 20 5 13 3 6 3 11 19 11 19 17 9 12 9 15 4 15 4 7 10 5 14 15 14 1 85812 94626 85812 91172 91172 93788 93788 96567 96567 75524 75524 23275 23275 98340 98340 81608 81608 91480 91480 75108 75108 56605 56605 93317 93317 41617 41617 77160 77160 727 727 7559...
output:
2568 612 8337 8985 3561 9182 649 301 2478 7307 2682 1175 1401 1268 8228 4407 109 2696 640 4478 3165 9184 21 8980 2092 9950 8009 9944 21 5038 87 2038 1881 19 1292 2183 336 1101 9386 3477 7723 1958 2741 1256 2331 715 21 545 21 448 699 2332 447 18 38 1424 2321 693 2459 21 2320 714 9999 8 196 1366 8933 ...
result:
wrong answer 2338th numbers differ - expected: '369', found: '370'
Subtask #4:
score: 10
Accepted
Test #13:
score: 10
Accepted
time: 793ms
memory: 156924kb
input:
1 200000 500000 189127 137023 189127 199761 199761 160701 160701 130639 130639 190908 190908 176819 176819 193363 193363 188021 188021 182446 182446 186028 186028 198828 198828 190792 190792 155378 155378 189428 189428 177276 177276 146159 146159 175923 175923 188073 188073 182206 182206 131072 1310...
output:
3782 1773 771 7328 18160 19394 1952 2 5498 2 2859 3368 7393 5131 5706 2 6001 19866 2 5123 2 12549 1497 4837 7770 16333 18175 5926 17983 19707 3821 17709 17094 4226 3822 576 5637 3660 4987 15686 2 18774 29 5068 16606 2276 16601 4544 598 845 19976 7054 882 164 2744 1683 6747 5091 1632 5137 2931 2778 1...
result:
ok 374196 numbers
Test #14:
score: 0
Accepted
time: 785ms
memory: 157660kb
input:
1 200000 500000 180482 179464 180482 193543 193543 198371 198371 169074 169074 164609 164609 168204 168204 197371 197371 173986 173986 182584 182584 173674 173674 181375 181375 190105 190105 186309 186309 189847 189847 168603 168603 99409 99409 185327 185327 172756 172756 99406 99406 185574 185574 1...
output:
10673 5634 7391 680 6687 12592 2003 4840 35 6181 17198 1362 3085 13905 1102 2869 1275 5446 4861 5644 2008 1518 20000 465 5127 2653 19817 779 2971 3892 5484 6267 1930 4344 263 789 7078 1447 2092 4322 3092 856 11362 19716 1105 2284 8702 4125 14956 11052 2786 4142 3437 9702 5492 3024 613 1707 16541 610...
result:
ok 374199 numbers
Subtask #5:
score: 0
Wrong Answer
Test #15:
score: 0
Wrong Answer
time: 1523ms
memory: 225960kb
input:
20 200000 1000000 13 10 13 5 19 5 19 20 15 10 15 6 12 6 12 3 8 10 8 2 1 20 1 11 14 10 14 16 18 3 18 7 4 3 9 10 9 17 194055 154514 194055 148156 148156 115271 115271 198116 198116 179433 179433 171975 171975 196600 196600 167194 167194 185078 185078 191409 191409 163496 163496 178243 178243 154093 15...
output:
459 5817 10120 7654 4894 19469 3577 16028 2835 7538 1131 9925 18495 497 11876 2132 9849 7576 7278 111 1850 7391 3350 6100 19488 16462 6207 1725 5922 5596 3820 1918 718 3319 2715 19890 5606 634 753 1301 15995 2973 1671 14675 5218 2639 118 1896 3266 1935 14603 4577 7219 5902 11027 4392 7461 9754 19632...
result:
wrong answer 8330th numbers differ - expected: '1687', found: '1688'