QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88364#5828. 游戏myee100 ✓541ms66036kbC++114.1kb2023-03-16 08:32:342023-03-16 08:32:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-16 08:32:36]
  • 评测
  • 测评结果:100
  • 用时:541ms
  • 内存:66036kb
  • [2023-03-16 08:32:34]
  • 提交

answer

#include <bits/stdc++.h>
typedef unsigned uint;
typedef long long llt;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _min(T&a,T b){return b<a?(a=b,true):false;}
template<typename T>bol _max(T&a,T b){return a<b?(a=b,true):false;}
inline uint lowbit(uint v){return v&-v;}
std::vector<uint>Way[200005];
std::vector<std::pair<uint,uint> >Dist[200005];
std::pair<uint,uint>MaxDist[200005];
uint Siz[200005],Dep[200005],Heavy[200005],Fath[200005],Dfn[200005],Rot[200005],End[200005],Back[200005],cnt;
voi dfs1(uint p,uint f){
    Siz[p]=1,Heavy[p]=-1,Fath[p]=f;
    for(auto s:Way[p])if(s!=f){
        Dep[s]=Dep[p]+1,dfs1(s,p),Siz[p]+=Siz[s],Dist[p].push_back({MaxDist[s].first+1,MaxDist[s].second});
        if(!~Heavy[p]||Siz[Heavy[p]]<Siz[s])Heavy[p]=s;
    }
    if(Dist[p].empty())Dist[p].push_back({0,p});
    MaxDist[p]=*std::max_element(Dist[p].begin(),Dist[p].end());
}
voi dfs2(uint p,uint r){
    std::sort(Dist[p].begin(),Dist[p].end()),std::reverse(Dist[p].begin(),Dist[p].end());
    Back[Dfn[p]=cnt++]=p,Rot[p]=r;
    if(~Heavy[p]){
        for(auto s:Way[p])if(s!=Fath[p])
            Dist[s].push_back(MaxDist[s].second==Dist[p][0].second?
                std::pair<uint,uint>{Dist[p][1].first+1,Dist[p][1].second}:
                std::pair<uint,uint>{Dist[p][0].first+1,Dist[p][0].second});
        dfs2(Heavy[p],r);for(auto s:Way[p])if(s!=Heavy[p]&&s!=Fath[p])dfs2(s,s);
    }
    End[p]=cnt;
}
uint lca(uint u,uint v){
    while(Rot[u]!=Rot[v]){
        if(Dep[Rot[u]]<Dep[Rot[v]])std::swap(u,v);
        u=Fath[Rot[u]];
    }
    return Dep[u]<Dep[v]?u:v;
}
uint kstep(uint u,uint v,uint k){
    uint r=lca(u,v);
    if(Dep[u]+Dep[v]-Dep[r]*2<k)return-1;
    if(Dep[u]-Dep[r]>=k){
        while(true){
            if(Dfn[u]-Dfn[Rot[u]]>=k)return Back[Dfn[u]-k];
            k-=Dfn[u]-Dfn[Rot[u]]+1,u=Fath[Rot[u]];
        }
    }
    else{
        k=Dep[u]+Dep[v]-Dep[r]*2-k;
        while(true){
            if(Dfn[v]-Dfn[Rot[v]]>=k)return Back[Dfn[v]-k];
            k-=Dfn[v]-Dfn[Rot[v]]+1,v=Fath[Rot[v]];
        }
    }
    return-1;
}
uint X[200005],Y[200005],Z[200005];
uint Max[200005],Mid[200005],Min[200005];
namespace BIT{
    std::pair<uint,uint>A[200005];
    voi chg(uint p,std::pair<uint,uint>v){
        p=200001-p;while(p<=200001)_max(A[p],v),p+=lowbit(p);
    }
    std::pair<uint,uint>find(uint p){
        std::pair<uint,uint>v;p=200001-p;
        while(p)_max(v,A[p]),p-=lowbit(p);
        return v;
    }
}
uint Ans[200005];
uint P1[200005],P2[200005];
int main(){
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#else
#endif
    uint n,q;scanf("%u",&n);
    for(uint i=1,u,v;i<n;i++)scanf("%u%u",&u,&v),Way[--u].push_back(--v),Way[v].push_back(u);
    dfs1(0,-1),Dist[0].push_back({0,0}),dfs2(0,0);
    for(uint i=0;i<n;i++)Dist[i].push_back({0,i}),P1[i]=i;
    scanf("%u",&q);
    for(uint i=0,x,y,z;i<q;i++)
        scanf("%u%u%u",&x,&y,&z),X[i]=(x+y-z)/2,Y[i]=(x-y+z)/2,Z[i]=(-x+y+z)/2,P2[i]=i,
        Max[i]=std::max({X[i],Y[i],Z[i]}),Min[i]=std::min({X[i],Y[i],Z[i]}),Mid[i]=X[i]+Y[i]+Z[i]-Max[i]-Min[i];
    std::sort(P1,P1+n,[&](uint a,uint b){return Dist[a][0]<Dist[b][0];});
    std::sort(P2,P2+q,[&](uint a,uint b){return Max[a]<Max[b];});
    for(uint i=n,j=q;j;){
        if(!i||Max[P2[j-1]]>Dist[P1[i-1]][0].first)
            j--,Ans[P2[j]]=BIT::find(Mid[P2[j]]).second;
        else
            i--,BIT::chg(Dist[P1[i]][1].first,{Dist[P1[i]][2].first,P1[i]});
    }
    for(uint i=0;i<q;i++){
        uint x=X[i],y=Y[i],z=Z[i],p=Ans[i];
        std::vector<std::pair<uint,uint> >V{Dist[p][2],Dist[p][1],Dist[p][0]};
        while(x>V[0].first||y>V[1].first||z>V[2].first)std::next_permutation(V.begin(),V.end());
        // printf("%u %u %u\n",x,y,z);
        // printf("%u %u %u\n",V[0].first,V[1].first,V[2].first);
        printf("%u %u %u\n",kstep(p,V[0].second,x)+1,kstep(p,V[1].second,y)+1,kstep(p,V[2].second,z)+1);
    }
    return 0;
}

/*
g++ game.cpp -o game -std=c++11 -Wall -DMYEE


*/


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 7ms
memory: 13076kb

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:

116 209 456
116 202 190
146 278 136
308 209 28
39 239 152
291 110 361
308 246 390
203 430 49
439 412 421
73 350 401
487 202 366
487 217 456
371 110 125
423 108 120
126 242 136
47 273 366
413 350 454
327 171 360
371 53 211
203 202 424
47 50 110
262 353 290
146 328 179
229 353 311
487 305 290
110 139 ...

result:

ok Accepted!

Test #2:

score: 10
Accepted
time: 3ms
memory: 13320kb

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:

1828 1000 175
101 1533 1242
653 1000 1105
870 769 1000
692 1343 1533
1285 646 120
1828 970 1242
1563 1991 727
1620 440 836
1436 1053 308
29 692 1414
1095 84 195
1108 217 809
1348 1039 1001
562 1039 977
286 1533 1257
1804 1533 1480
989 1846 666
652 1950 1672
1848 1734 1948
1343 409 105
1458 368 664
1...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 330ms
memory: 39440kb

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:

183588 127372 141391

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 334ms
memory: 39484kb

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:

30648 7276 95506

result:

ok Accepted!

Test #5:

score: 10
Accepted
time: 313ms
memory: 39820kb

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:

107898 24423 35469
39355 49857 70450
43197 10301 17387
188745 112648 172547
28667 74366 89391
47753 111291 33917
86727 124776 193560
181288 21360 193823
11243 105792 168605
40218 35115 97478

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 332ms
memory: 39624kb

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:

160968 71887 172972
175224 3301 155718
136255 99663 8719
197332 74888 15491
147837 75665 40179
61618 118762 187886
54450 79528 148651
84433 110284 125308
99168 122489 43978
142520 126427 172234

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 290ms
memory: 66036kb

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: 431ms
memory: 45708kb

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 4704
197325 197325 10591
56264 56264 38396
197325 197325 109303
197325 197325 79504
197325 197325 99289
197325 197325 69799
197325 197325 174490
197325 197325 126621
197325 197325 140463
197325 197325 167534
197325 197325 102608
197325 197325 12754
197325 197325 186281
197325 197325 15...

result:

ok Accepted!

Test #9:

score: 10
Accepted
time: 541ms
memory: 45612kb

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:

16852 161600 144003
147087 56002 142950
104657 112119 167698
134920 74246 195552
179029 120520 174842
151828 178802 52714
139667 178393 173324
196768 107997 93428
155312 21334 5823
94741 188561 160574
102834 20580 117724
152664 78138 113665
112847 16594 9478
122793 182002 61063
122944 178243 135823
...

result:

ok Accepted!

Test #10:

score: 10
Accepted
time: 474ms
memory: 45740kb

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:

77819 23373 20019
95761 11770 131379
2614 160961 93061
188210 40546 191755
41838 63792 156254
179500 1353 26124
85691 166930 65243
88067 3669 192149
143997 41973 105686
137988 168152 59440
73735 90970 182873
112218 118619 42991
92721 49370 7976
95660 168939 35969
17492 38268 22990
172124 50538 86583...

result:

ok Accepted!

Extra Test:

score: 0
Extra Test Passed