QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#208573#5828. 游戏Williamxzh100 ✓312ms78044kbC++144.2kb2023-10-09 19:00:412023-10-09 19:00:41

Judging History

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

  • [2023-10-09 19:00:41]
  • 评测
  • 测评结果:100
  • 用时:312ms
  • 内存:78044kb
  • [2023-10-09 19:00:41]
  • 提交

answer

#pragma GCC optimize("O2,O3,Ofast,inline,unroll-loops")
#pragma GCC target("avx2,sse4")
#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+5;
int n,Q,fa[N][20],de[N],lg[N];pii mx[N][3];
vector<int> e[N];
il void add(int x,int y){e[x].push_back(y);}
void dfs(int x,int fath){
    pii u;fa[x][0]=fath,de[x]=de[fath]+1;
    for(int i=0;i<3;++i) mx[x][i]={0,x};
    for(int i=1;i<=18;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int y : e[x]){
        if(y==fath) continue;
        dfs(y,x),u=mx[y][0],++u.fi;
        for(int i=0;i<3;++i) if(u>=mx[x][i]) swap(u,mx[x][i]);
    }
}
void dfs1(int x,int fath,pii u){
    pii v;
    for(int i=0;i<3;++i) if(u>=mx[x][i]) swap(u,mx[x][i]);
    for(int y : e[x]){
        if(y==fath) continue;
        v=(mx[x][0].se==mx[y][0].se?mx[x][1]:mx[x][0]),++v.fi,v=max(v,u);
        dfs1(y,x,v);
    }
}
il int lca(int x,int y){
    if(de[x]<de[y]) swap(x,y);
    while(de[x]>de[y]) x=fa[x][lg[de[x]-de[y]]-1];
    if(x==y) return x;
    for(int i=18;i>=0;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
il int jump(int x,int k){
    for(int i=18;i>=0;--i) if(de[x]-de[fa[x][i]]<=k) k-=de[x]-de[fa[x][i]],x=fa[x][i];
    return x;
}
il int get(int s,int t,int k){
    int x=lca(s,t),y=de[s]-de[x],z=de[t]-de[x];
    if(s==x) return jump(t,z-k);
    if(y>=k) return jump(s,k);
    else return jump(t,y+z-k);
}
il bool cmp(int x,int y){
    return mx[x][0].fi==mx[y][0].fi?(mx[x][1].fi==mx[y][1].fi?mx[x][2].fi<mx[y][2].fi:mx[x][1].fi<mx[y][1].fi):mx[x][0].fi<mx[y][0].fi;
}
vector<int> f[N];
struct node{
    int x,y,z;
    il node(){x=y=z=0;}
    il node(int x,int y,int z) : x(x),y(y),z(z) {}
}q[N];
vector<pii> g[N];
int tree[N<<2];
il void pushup(int x){tree[x]=(mx[tree[x<<1]][2].fi>=mx[tree[x<<1|1]][2].fi?tree[x<<1]:tree[x<<1|1]);}
il void update(int x,int l,int r,int p,int u){
    if(l==r){tree[x]=(mx[u][2].fi>=mx[tree[x]][2].fi?u:tree[x]);return ;}
    int mid=(l+r)>>1;
    if(p<=mid) update(x<<1,l,mid,p,u);
    else update(x<<1|1,mid+1,r,p,u);
    pushup(x);
}
int query(int x,int l,int r,int L,int R){
    if(l>=L && r<=R) return tree[x];
    int mid=(l+r)>>1,ret=0,u;
    if(L<=mid){
        u=query(x<<1,l,mid,L,R);
        if(!ret || mx[ret][2].fi<mx[u][2].fi) ret=u;
    }
    if(R>mid){
        u=query(x<<1|1,mid+1,r,L,R);
        if(!ret || mx[ret][2].fi<mx[u][2].fi) ret=u;
    }
    return ret;
}
int x,y,z,u,v,w,p,a[3],ans[N];
int main(){
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for(int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;
    dfs(1,0),dfs1(1,0,{0,0});
    for(int i=1;i<=n;++i) f[mx[i][0].fi].push_back(i);
    scanf("%d",&Q);
    for(int i=1;i<=Q;++i){
        scanf("%d%d%d",&x,&y,&z);
        u=(x+y-z)>>1,v=(x-y+z)>>1,w=(y+z-x)>>1,a[0]=u,a[1]=v,a[2]=w,q[i]=node(u,v,w);sort(a,a+3);
        g[a[2]].push_back({i,a[1]});
    }
    for(int i=n;~i;--i){
        for(int x : f[i]) update(1,0,n,mx[x][1].fi,x);
        for(pii x : g[i])  ans[x.fi]=query(1,0,n,x.se,n);
    }
    for(int i=1;i<=Q;++i){
        p=ans[i],x=q[i].x,y=q[i].y,z=q[i].z;
        if(mx[p][0].fi>=x && mx[p][1].fi>=y && mx[p][2].fi>=z) printf("%d %d %d\n",get(p,mx[p][0].se,x),get(p,mx[p][1].se,y),get(p,mx[p][2].se,z));
        else if(mx[p][0].fi>=x && mx[p][2].fi>=y && mx[p][1].fi>=z) printf("%d %d %d\n",get(p,mx[p][0].se,x),get(p,mx[p][2].se,y),get(p,mx[p][1].se,z));
        else if(mx[p][1].fi>=x && mx[p][0].fi>=y && mx[p][2].fi>=z) printf("%d %d %d\n",get(p,mx[p][1].se,x),get(p,mx[p][0].se,y),get(p,mx[p][2].se,z));
        else if(mx[p][1].fi>=x && mx[p][2].fi>=y && mx[p][0].fi>=z) printf("%d %d %d\n",get(p,mx[p][1].se,x),get(p,mx[p][2].se,y),get(p,mx[p][0].se,z));
        else if(mx[p][2].fi>=x && mx[p][0].fi>=y && mx[p][1].fi>=z) printf("%d %d %d\n",get(p,mx[p][2].se,x),get(p,mx[p][0].se,y),get(p,mx[p][1].se,z));
        else if(mx[p][2].fi>=x && mx[p][1].fi>=y && mx[p][0].fi>=z) printf("%d %d %d\n",get(p,mx[p][2].se,x),get(p,mx[p][1].se,y),get(p,mx[p][0].se,z));
    }
    return 0;
}

详细

Test #1:

score: 10
Accepted
time: 0ms
memory: 22328kb

input:

500
279 196
182 105
400 14
278 217
198 411
379 318
120 421
314 95
437 325
23 433
71 485
192 154
90 224
180 71
328 93
183 101
404 349
223 285
492 100
366 480
29 328
200 448
365 156
226 231
129 167
246 273
171 452
284 6
131 471
229 90
480 48
448 157
240 221
7 36
401 200
255 438
436 110
281 489
388 258...

output:

421 209 365
421 202 420
361 278 175
343 209 473
436 420 57
30 110 146
343 246 7
158 430 47
179 412 116
120 350 435
215 202 378
215 217 365
253 110 126
311 108 73
125 242 175
49 273 378
306 350 344
278 228 360
253 53 262
158 202 36
202 50 110
211 353 406
361 328 439
17 353 423
215 305 406
110 139 7
3...

result:

ok Accepted!

Test #2:

score: 10
Accepted
time: 6ms
memory: 24600kb

input:

2000
643 1871
689 23
1822 1443
1031 1027
1655 845
189 771
1561 498
19 1778
576 1080
904 717
1690 291
1387 1077
398 811
1310 1231
645 1291
480 927
330 170
1464 1057
1033 894
1308 288
1292 1529
1212 122
1108 401
89 1118
1058 1088
1764 1314
981 1255
1893 864
180 1887
1903 843
734 1412
883 1013
1739 124...

output:

1995 1000 761
528 1533 1738
809 1000 1003
870 831 1000
692 1227 898
109 646 726
1995 970 1738
1030 1991 1758
1390 440 1095
339 1053 439
586 692 1702
836 413 471
1574 217 653
1201 1039 1804
664 1039 402
158 1533 174
1001 1533 1343
989 1991 735
1783 1950 1758
1447 1734 1049
1480 409 843
1366 368 562
1...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 85ms
memory: 54056kb

input:

200000
56968 132021
105656 107536
123627 58349
119191 138198
133708 142638
114350 24980
137784 40346
124158 130204
80684 183207
78156 94449
21893 157560
54464 73571
145830 57756
160288 32120
178632 142663
26565 185985
70576 24906
32217 115826
185756 137673
54280 179613
77826 144447
66005 29955
11745...

output:

87763 127372 167377

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 90ms
memory: 53492kb

input:

200000
41999 100683
85781 129266
122431 179332
162416 44814
24405 42267
154161 12483
178049 159964
67625 152391
133072 25866
178005 14695
94384 170290
54701 40323
66280 128515
159022 55057
14985 12920
182805 40659
173117 67973
99771 26102
198919 94543
23608 187601
61125 5759
89437 47647
18142 192402...

output:

82066 7276 199629

result:

ok Accepted!

Test #5:

score: 10
Accepted
time: 96ms
memory: 50784kb

input:

200000
195072 75458
31991 127114
60943 49502
186375 1130
45394 147217
168455 84307
132752 188952
101108 130004
107490 22003
16275 187645
111002 42669
138880 137115
112688 172751
81697 99037
166996 18495
2234 56119
170807 101349
105736 23180
148159 40863
136678 11849
190707 91245
61779 120740
157115 ...

output:

34411 24423 130978
39355 108717 46584
52145 10301 66653
129196 118391 75453
96028 74366 93926
194867 26201 124636
193249 124776 8021
36173 21360 118748
16928 105792 116603
197158 35115 78006

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 93ms
memory: 53932kb

input:

200000
48556 78408
155026 9376
8983 61211
150393 85068
90892 109283
75746 89742
6760 187245
168658 130735
68602 127646
60802 149828
22898 59471
172845 100274
42303 190696
7612 134905
94702 59800
129633 192496
19903 64869
51318 63358
34692 66030
98535 176606
153647 177529
157903 147292
106273 107278
...

output:

145500 71887 100276
156481 3301 65860
134802 99663 157918
126929 74888 4153
79250 75665 19591
31684 118762 29616
77495 79528 148651
49868 110284 99352
12157 122489 51911
82672 126427 64004

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 312ms
memory: 78044kb

input:

200000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 5...

output:

54356 200000 137052
200000 170197 131241
84517 200000 179296
183330 163219 200000
158370 200000 194345
85385 171870 200000
143829 200000 85216
200000 122372 28132
200000 25711 157674
200000 179037 24813
200000 197101 57460
117928 178289 200000
200000 179418 195973
22762 116045 200000
100818 200000 1...

result:

ok Accepted!

Test #8:

score: 10
Accepted
time: 176ms
memory: 54220kb

input:

200000
5732 55198
128966 25317
114737 116391
150003 18274
43867 70745
76222 4169
55976 114951
198396 72896
38647 19711
12756 172119
73197 117994
117512 14177
130965 126990
119440 183341
142023 60829
111893 57350
122754 123305
36525 79077
36447 91967
135405 170456
165839 147481
66074 175822
22238 264...

output:

197325 197325 70254
197325 197325 155225
56264 56264 38396
197325 197325 173619
197325 197325 95661
197325 197325 156174
197325 197325 138343
197325 197325 29777
197325 197325 188592
197325 197325 107966
197325 197325 107552
197325 197325 44079
197325 197325 193253
197325 197325 99075
197325 197325 ...

result:

ok Accepted!

Test #9:

score: 10
Accepted
time: 234ms
memory: 56868kb

input:

200000
185063 17064
180987 114492
88071 71803
158363 135918
60910 54848
97338 6734
192937 9410
49617 199068
82499 63554
188791 188152
178767 40866
11304 27212
144234 138097
42236 3946
103355 12683
50992 20598
145723 48620
11709 115688
123172 121379
70541 130844
147827 39431
139372 61280
42705 54015
...

output:

80097 161600 36567
66894 56002 38634
184795 112119 193267
165046 74246 102483
66610 120520 160376
119681 178802 87450
113149 178393 172202
83964 107997 180100
99848 21334 5957
75873 188561 184300
119888 20580 66285
44224 78138 151916
151223 16594 71093
3957 182002 80938
82137 178243 159894
99825 120...

result:

ok Accepted!

Test #10:

score: 10
Accepted
time: 232ms
memory: 54624kb

input:

200000
197244 185999
18639 124754
154223 12099
53676 167616
22710 22294
150412 66132
19320 75478
170410 122661
130961 175554
171586 85572
188386 81238
120249 117687
43214 126266
8744 165654
164725 189519
124144 170329
86605 100197
130545 17030
113301 96665
67733 187286
37846 146399
75352 117550
3235...

output:

46612 23373 84089
74523 11770 103058
113594 160961 4313
25740 40546 64481
184978 63792 71292
163893 1353 78456
130689 166930 162505
166586 3669 94060
21175 41973 74478
134043 168152 30888
3992 90970 93502
17316 118619 100001
77703 49370 42008
95660 168939 168135
55180 38268 109017
100828 50538 16609...

result:

ok Accepted!

Extra Test:

score: 0
Extra Test Passed