QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318999#5828. 游戏KiharaTouma100 ✓383ms127592kbC++239.9kb2024-02-01 14:42:012024-02-01 14:42:02

Judging History

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

  • [2024-02-01 14:42:02]
  • 评测
  • 测评结果:100
  • 用时:383ms
  • 内存:127592kb
  • [2024-02-01 14:42:01]
  • 提交

answer

//qoj5828
#include <bits/stdc++.h>
using namespace std; typedef long long ll; namespace FastIO {
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc() { if (__builtin_expect(_read_ptr == _read_ptr_end, false)) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;} return *_read_ptr++; }
INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } }
INLINE_V struct _auto_flush { ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; inline bool _isdigit(char c) { return (c & 16) && c != EOF; } inline bool _isgraph(char c) { return c > 32 && c != EOF; }
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer; template <class T> INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed; template <class T> INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <> INLINE_V constexpr bool _is_integer<__int128> = true; template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true; template <> INLINE_V constexpr bool _is_signed<__int128> = true; template <> INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
inline void read(char &c) { do c = gc(); while (!_isgraph(c)); } inline void read_cstr(char *s) { char c = gc(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) s.push_back(c), c = gc(); }
template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void read(T &x) { char c = gc(); bool f = true; x = 0; while (!_isdigit(c)) { if (c == 45) f = false; c = gc(); }
if (f) while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); else while (_isdigit(c)) x = x * 10 - (c & 15), c = gc(); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void read(T &x) { char c = gc(); while (!_isdigit(c)) c = gc(); x = 0; while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); }
inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while (*s) pc(*s++); } inline void write(const string &s) { for (char c : s) pc(c); } template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; if (x >= 0) do buffer[digits++] = (x % 10) | 48, x /= 10; while (x);
else { pc(45); do buffer[digits++] = -(x % 10) | 48, x /= 10; while (x); } while (digits) pc(buffer[--digits]); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; do buffer[digits++] = (x % 10) | 48, x /= 10; while (x); while (digits) pc(buffer[--digits]); }
template <int N> struct _tuple_io_helper { template <class... T> static inline void _read(tuple<T...> &x) { _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x)); } };
template <> struct _tuple_io_helper<1> { template <class... T> static inline void _read(tuple<T...> &x) { read(get<0>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { write(get<0>(x)); } };
template <class... T> inline void read(tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_read(x); } template <class... T> inline void write(const tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_write(x); }
template <class T1, class T2> inline void read(pair<T1, T2> &x) { read(x.first), read(x.second); } template <class T1, class T2> inline void write(const pair<T1, T2> &x) { write(x.first), pc(32), write(x.second); }
template <class T1, class... T2> inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template <class... T> inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template <class T1, class... T2> inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template <class... T> inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template <class T> inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template <class T1, class... T2> inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template <class... T> inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); }
template <class... T> inline void println(const T &...x) { print(x...), pc(10); } template <class... T> inline void printk(const T &...x) { print(x...), pc(32); } template <class... T> inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO; void solve();int main(){ solve(); return 0; }

const int N = 2e5 + 10;
int n, q, dep[N], mxd[N], mxo[N], f[N][4], fat[N][20];
int qu[N], qv[N], qw[N], au[N], av[N], aw[N], t[N*4], rt[N*4];
vector<pair<int, pair<int, int> > > ad[N], qr[N];
pair<int, int> fr[N][4];
vector<int> g[N];

void dfs1(int x, int fa){
	mxd[x] = dep[x] = dep[fa] + 1;
	mxo[x] = x;
	fat[x][0] = fa;
	for(int i = 1; i < 20; ++ i){
		fat[x][i] = fat[fat[x][i-1]][i-1];
	}
	for(int y : g[x]){
		if(y == fa){
			continue;
		}
		dfs1(y, x);
		pair<int, pair<int, int> > tmp[5];
		for(int i = 0; i < 4; ++ i){
			tmp[i] = make_pair(f[x][i], fr[x][i]);
		}
		tmp[4] = make_pair(mxd[y], make_pair(y, mxo[y]));
		sort(tmp, tmp + 5);
		reverse(tmp, tmp + 5);
		for(int i = 0; i < 4; ++ i){
			tie(f[x][i], fr[x][i]) = tmp[i];
		}
		if(mxd[y] > mxd[x]){
			mxd[x] = mxd[y];
			mxo[x] = mxo[y];
		}
	}
}
void dfs2(int x, int fa){
	for(int y : g[x]){
		if(y == fa){
			continue;
		}
		pair<int, pair<int, int> > tmp[5];
		for(int i = 0; i < 4; ++ i){
			tmp[i] = make_pair(max(0, f[y][i] - dep[y]), fr[y][i]);
		}
		if(fr[x][0].first != y){
			tmp[4] = make_pair(f[x][0] + 1, make_pair(x, fr[x][0].second));
		} else {
			tmp[4] = make_pair(f[x][1] + 1, make_pair(x, fr[x][1].second));
		}
		sort(tmp, tmp + 5);
		reverse(tmp, tmp + 5);
		for(int i = 0; i < 4; ++ i){
			tie(f[y][i], fr[y][i]) = tmp[i];
		}
		dfs2(y, x);
	}
}
int lca(int x, int y){
	if(dep[x] < dep[y]){
		swap(x, y);
	}
	for(int i = 19; i >= 0; -- i){
		if(dep[fat[x][i]] >= dep[y]){
			x = fat[x][i];
		}
	}
	if(x == y){
		return x;
	}
	for(int i = 19; i >= 0; -- i){
		if(fat[x][i] != fat[y][i]){
			x = fat[x][i];
			y = fat[y][i];
		}
	}
	return fat[x][0];
}
int jmp(int x, int d){
	for(int i = 19; i >= 0; -- i){
		if(d & (1 << i)){
			x = fat[x][i];
		}
	}
	return x;
}
int mv(int x, int y, int d){
	int l = lca(x, y);
	if(dep[x] - dep[l] < d){
		d -= dep[x] - dep[l];
		return mv(y, l, dep[y] - dep[l] - d);
	} else {
		return jmp(x, d);
	}
}

void add(int p, int l, int r, int x, int v, int rr){
	if(l == r){
		if(v > t[p]){
			t[p] = v;
			rt[p] = rr;
		}
	} else {
		int mid = l + r >> 1;
		if(x <= mid){
			add(p<<1, l, mid, x, v, rr);
		} else {
			add(p<<1|1, mid+1, r, x, v, rr);
		}
		if(t[p<<1] > t[p<<1|1]){
			t[p] = t[p<<1];
			rt[p] = rt[p<<1];
		} else {
			t[p] = t[p<<1|1];
			rt[p] = rt[p<<1|1];
		}
	}
}
pair<int, int> ask(int p, int l, int r, int ql, int qr){
	if(qr < l || r < ql){
		return make_pair(-114, 0);
	} else if(ql <= l && r <= qr){
		return make_pair(t[p], rt[p]);
	} else {
		int mid = l + r >> 1;
		return max(ask(p<<1, l, mid, ql, qr), ask(p<<1|1, mid+1, r, ql, qr));
	}
}

void solve(){
	read(n);
	for(int i = 1; i < n; ++ i){
		int u, v;
		read(u, v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1, 0);
	for(int i = 0; i < 4; ++ i){
		if(f[1][i] > 0){
			-- f[1][i];
		} else {
			f[1][i] = 0;
			fr[1][i] = make_pair(1, 1);
		}
	}
	dfs2(1, 0);
	for(int i = 1; i <= n; ++ i){
		if(!f[i][1]){
			continue;
			fr[i][1] = make_pair(i, i);
		}
		if(!f[i][2]){
			fr[i][2] = make_pair(i, i);
		}
		ad[f[i][0]].emplace_back(f[i][1], make_pair(f[i][2], i));
		ad[f[i][0]].emplace_back(f[i][2], make_pair(f[i][1], i));
		ad[f[i][1]].emplace_back(f[i][0], make_pair(f[i][2], i));
		ad[f[i][1]].emplace_back(f[i][2], make_pair(f[i][0], i));
		ad[f[i][2]].emplace_back(f[i][0], make_pair(f[i][1], i));
		ad[f[i][2]].emplace_back(f[i][1], make_pair(f[i][0], i));
	}
	read(q);
	for(int i = 1; i <= q; ++ i){
		int x, y, z, t[3];
		read(x, y, z);
		t[0] = (x + y - z) / 2;
		t[1] = (x + z - y) / 2;
		t[2] = (y + z - x) / 2;
		qu[i] = t[0];
		qv[i] = t[1];
		qw[i] = t[2];
		qr[t[0]].emplace_back(t[1], make_pair(t[2], i));
	}
	memset(t, -1, sizeof(t));
	for(int i = n; i >= 0; -- i){
		for(auto j : ad[i]){
			add(1, 0, n, j.first, j.second.first, j.second.second);
		}
		for(auto j : qr[i]){
			auto x = ask(1, 0, n, j.first, n);
			if(x.first >= j.second.first){
				au[j.second.second] = x.second;
			}
		}
	}
	for(int i = 1; i <= q; ++ i){
		int r = au[i];
		int a1 = (qu[i] > qv[i] ? 0 : 1) + (qu[i] > qw[i] ? 0 : 1);
		int a2 = (qv[i] >= qu[i] ? 0 : 1) + (qv[i] > qw[i] ? 0 : 1);
		int a3 = (qw[i] >= qu[i] ? 0 : 1) + (qw[i] >= qv[i] ? 0 : 1);
		int x = mv(fr[r][a1].second, r, f[r][a1] - qu[i]);
		int y = mv(fr[r][a2].second, r, f[r][a2] - qv[i]);
		int z = mv(fr[r][a3].second, r, f[r][a3] - qw[i]);
		println(x, y, z);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 2ms
memory: 18184kb

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:

241 295 342
136 485 81
361 278 175
29 253 327
297 386 305
57 64 461
29 227 100
207 443 476
399 268 30
215 116 257
366 360 427
183 74 270
57 93 401
275 463 361
17 333 285
242 306 82
477 60 431
496 247 211
74 323 39
17 48 219
202 50 110
227 262 78
478 454 80
270 180 217
123 165 106
30 168 366
242 125 ...

result:

ok Accepted!

Test #2:

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

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:

169 44 1600
474 546 688
1425 1118 1633
555 356 1152
134 1840 1973
1252 608 1495
798 1262 1738
1065 1784 418
1283 211 1532
1498 608 971
223 620 217
1495 261 1201
1717 232 793
856 1326 1030
886 1091 895
809 680 1920
1565 680 865
1672 727 1960
1094 469 1498
1445 1134 722
466 1703 1897
265 1734 1043
282...

result:

ok Accepted!

Test #3:

score: 10
Accepted
time: 246ms
memory: 71540kb

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:

776 87237 28828

result:

ok Accepted!

Test #4:

score: 10
Accepted
time: 229ms
memory: 72204kb

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:

178959 179424 99114

result:

ok Accepted!

Test #5:

score: 10
Accepted
time: 226ms
memory: 71984kb

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:

151908 100567 8721
83205 59848 186152
77586 20873 189692
82637 19743 158643
57450 78922 97078
8412 35694 91454
150386 21717 136838
36808 82816 94104
176048 3051 100174
66824 169604 86044

result:

ok Accepted!

Test #6:

score: 10
Accepted
time: 226ms
memory: 71740kb

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:

106922 97132 138890
76437 85688 53605
116888 61263 21725
40657 108839 54522
195824 177152 19728
112642 70748 24715
183291 31534 40603
100096 93881 177689
153396 122160 23021
64257 48141 90870

result:

ok Accepted!

Test #7:

score: 10
Accepted
time: 319ms
memory: 127592kb

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:

182696 37052 100000
1 29804 68760
194779 79296 100000
20112 40223 3442
135975 94345 100000
172971 86486 58356
56172 1 114785
1 77629 171869
25711 200000 68037
1 20964 175188
1 2900 142541
120723 60362 38651
95973 116555 100000
186567 93284 9329
191033 91851 100000
164273 82137 69295
1 19612 136758
6...

result:

ok Accepted!

Test #8:

score: 10
Accepted
time: 304ms
memory: 76600kb

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:

175386 175386 170727
175386 175386 110841
175386 175386 76386
175386 175386 74708
175386 175386 126745
175386 175386 185798
175386 175386 27903
175386 175386 157263
175386 175386 151499
175386 175386 125962
175386 175386 135498
175386 175386 142371
175386 175386 48782
175386 175386 120715
175386 175...

result:

ok Accepted!

Test #9:

score: 10
Accepted
time: 362ms
memory: 74580kb

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:

174856 71977 179574
3000 92997 150200
131745 178675 129413
23537 16791 163698
84168 139606 59302
45133 102212 129450
36071 66590 179652
10044 8498 121963
154803 72889 112576
103298 92023 149577
62393 52491 110120
36176 53316 130529
26773 72903 37916
196111 29472 143001
67960 158987 166223
109155 751...

result:

ok Accepted!

Test #10:

score: 10
Accepted
time: 383ms
memory: 74632kb

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:

135279 172309 119889
91745 39778 86165
81355 142861 110998
45021 101167 129885
15533 113720 195317
150042 173590 178458
23433 6693 186485
93168 84744 130124
16343 15187 47670
74142 25823 118876
105696 6646 116532
69796 185386 107065
117608 173194 102909
134958 151855 175566
95136 59440 76341
128223 ...

result:

ok Accepted!

Extra Test:

score: 0
Extra Test Passed