QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#371682#4891. 树上的孤独zsq14725836930 1523ms225960kbC++173.2kb2024-03-30 14:56:302024-03-30 14:56:31

Judging History

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

  • [2024-03-30 14:56:31]
  • 评测
  • 测评结果:30
  • 用时:1523ms
  • 内存:225960kb
  • [2024-03-30 14:56:30]
  • 提交

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'