QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#125495#5828. 游戏orz_z0 741ms77424kbC++145.6kb2023-07-16 19:03:412023-07-16 19:03:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 19:03:42]
  • 评测
  • 测评结果:0
  • 用时:741ms
  • 内存:77424kb
  • [2023-07-16 19:03:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
// #define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define each(i, v) for(auto i : v)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug debug("Passing [%s] in LINS %d\n", __FUNCTION__, __LINE__)
#define pb push_back
#define fi first
#define se second
#define Mry debug("%.3lf MB\n", (&Mbe - &Med) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
	int x = 0;
	bool t = 0;
	char c = getchar();
	while (c < '0' || c > '9') t |= c == '-', c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return t ? -x : x;
}
inline void wi(int x) {
	if (x < 0) {
		putchar('-'), x = -x;
	}
	if (x > 9) wi(x / 10);
	putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
	wi(x), putchar(s);
}
bool Mbe;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;


namespace GAME {
	int n, q;
	vi d[_];
	namespace Tree {
		int f[20][_], dep[_];
		void dfs(int u, int fa) {
			dep[u] = dep[fa] + 1, f[0][u] = fa;
			for(int v : d[u]) if(v != fa) dfs(v, u);
		}
		void init() {
			dfs(1, 0);
			F(i, 1, 19) F(j, 1, n) f[i][j] = f[i - 1][f[i - 1][j]];
		}
		int jump(int x, int d) {
//			assert(x), assert(d >= 0), assert(d < dep[x]);
//			cout << "jump : " << x << ' ' << d << ' ';
			dF(i, 19, 0) if((d >> i) & 1) x = f[i][x];
//			cout << x << '\n';
			return x;
		}
		int LCA(int u, int v) {
			if(dep[u] < dep[v]) swap(u, v);
			dF(i, 19, 0) if(dep[f[i][u]] >= dep[v]) u = f[i][u];
			if(u == v) return u;
			dF(i, 19, 0) if(f[i][u] != f[i][v]) u = f[i][u], v = f[i][v];
			return f[0][u];
		}
		int Dis(int u, int v) {
			return dep[u] + dep[v] - (dep[LCA(u, v)] << 1);
		}
	}
	namespace HG {
		struct node {
			int ln, v, v2;
			node() {
			}
			node(int Ln = 0, int V = 0, int V2 = 0) {
				ln = Ln, v = V, v2 = V2;
			}
		};
		vector<node> g[_];
		int len[_], p[_], p2[_];
		int dfs(int u, int fa) {
			g[u].clear();
			len[u] = 0;
			int p = 0;
			for(int v : d[u]) if(v != fa){
				int w = dfs(v, u);
				if(len[u] < len[v] + 1) {
					len[u] = len[v] + 1;
					p = w;
				}
				g[u].pb(node(len[v] + 1, v, w));
			}
			sort(g[u].begin(), g[u].end(), [&](node a, node b) { return a.ln > b.ln; });
			while(g[u].size() > 3) g[u].pop_back();
			while(g[u].size() < 3) g[u].pb(node(0, 0, u));
			if(d[u].size() == 1) return u;
			else return p;
//			while(!g[u].empty() && g[u].back() == 0) g[u].pop_back();
		}
		void dfs2(int u, int fa, int ln) {
			if(fa && ln) {
				g[u].pb(node(ln, fa, 0));
				sort(g[u].begin(), g[u].end(), [&](node a, node b) { return a.ln > b.ln; });
			}
			while(g[u].size() > 3) g[u].pop_back();
			while(g[u].size() < 3) g[u].pb(node(0, 0, 0));
			int nw = 0;
			for(int v : d[u]) if(v != fa) {
				nw = 0;
				if(g[u][0].v == v) nw = g[u][1].ln;
				else nw = g[u][0].ln;
				dfs2(v, u, nw + 1);
			}
		}
		void init() {
			dfs(1, 0), dfs2(1, 0, 0);
		}
	}
	namespace CDQ {
		int as[_];
		struct qry {
			int x, y, z, d, a, b, c; // a--u, b -- v, c -- w
			vector<pii> g;
			int pos[3];
			qry() {}
			qry(int X, int Y, int Z) {
				x = X, y = Y, z = Z;
				d = (x + y + z) / 2;
				a = d - z, b = d- y, c = d - x;
				g.pb({a, 0}), g.pb({b, 1}), g.pb({c, 2});
				sort(g.begin(), g.end(), [&](pii a, pii b) { return a > b; });
				F(i, 0, 2) pos[g[i].se] = i;
			}
		} qr[_];
		// find u, st. g[u][0] >= a, g[u][1] >= b, g[u][c] >= c
		void init() {
			F(i, 1, q) {
				F(j, 1, n) if(HG::g[j][0].ln >= qr[i].g[0].fi && HG::g[j][1].ln >= qr[i].g[1].fi && HG::g[j][2].ln >= qr[i].g[2].fi) {
					as[i] = j; break;
				}
			}
		}
	}
	namespace Gas {
		int ans[_][3];
		void init() {
			F(i, 1, q) {
				int x = CDQ::as[i];
				F(j, 0, 2) {
					assert(HG::g[x][j].ln >= CDQ::qr[i].g[j].fi);
					if(HG::g[x][j].v2 == 0) {
						cout << HG::g[x][j].ln << ' ' << HG::g[x][j].v << ' ' << HG::g[x][j].v2 << ' ' << Tree::f[0][x] << ' ' << CDQ::qr[i].g[j].fi << '\n';
//						assert((HG::g[x][j].ln == 0 && HG::g[x][j].v == 0) || (HG::g[x][j].v == Tree::f[x][0] && HG::g[x][j].ln > 0));
						ans[i][j] = Tree::jump(x, CDQ::qr[i].g[j].fi);
//					if(!ans[i][j]) ans[i][j] = x;
					} else {
						ans[i][j] = Tree::jump(HG::g[x][j].v2, HG::g[x][j].ln - CDQ::qr[i].g[j].fi);
//					if(!ans[i][j]) ans[i][j] = x;
					}
				}
			}
			F(i, 1, q) cout << ans[i][CDQ::qr[i].pos[0]] << ' ' << ans[i][CDQ::qr[i].pos[1]] << ' ' << ans[i][CDQ::qr[i].pos[2]] << '\n';
		}
	}
} using namespace GAME;
bool Med;
signed main() {
	// Mry;
	n = ri();
	F(i, 1, n - 1) {
		int u = ri(), v  =ri();
		d[u].pb(v), d[v].pb(u);
	}
	Tree::init(), HG::init();
	q = ri();
	F(i, 1, q) {
		int x = ri(), y = ri(), z = ri();
		CDQ::qr[i] = CDQ::qry(x, y, z);
	}
	CDQ::init();
	Gas::init();
	// Try;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 47788kb

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:

53 110 0 110 43
54 200 0 200 35
53 110 0 110 38
54 200 0 200 25
54 200 0 200 50
54 200 0 200 26
54 200 0 200 37
54 200 0 200 35
54 200 0 200 34
54 200 0 200 20
54 200 0 200 43
72 490 0 490 37
54 200 0 200 47
53 110 0 110 40
54 200 0 200 27
54 200 0 200 36
23 492 0 492 21
54 200 0 200 30
54 200 0 200...

result:

wrong answer Integer 0 violates the range [1, 500]

Test #2:

score: 0
Wrong Answer
time: 8ms
memory: 47288kb

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:

320 272 0 272 101
151 577 0 577 100
81 1193 0 1193 80
320 272 0 272 163
151 577 0 577 51
151 577 0 577 46
124 761 0 761 100
151 577 0 577 26
151 577 0 577 30
151 577 0 577 68
151 577 0 577 31
151 577 0 577 18
151 577 0 577 63
151 577 0 577 45
151 577 0 577 61
151 577 0 577 51
151 577 0 577 51
151 57...

result:

wrong answer Integer 0 violates the range [1, 2000]

Test #3:

score: 0
Wrong Answer
time: 105ms
memory: 67192kb

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:

4239 174945 0 174945 1843
178310 71361 45838

result:

wrong answer Integer 0 violates the range [1, 200000]

Test #4:

score: 0
Wrong Answer
time: 129ms
memory: 67364kb

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:

3676 29571 0 29571 1017
114360 24899 74592

result:

wrong answer Integer 0 violates the range [1, 200000]

Test #5:

score: 0
Wrong Answer
time: 137ms
memory: 66216kb

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:

5096 74283 0 74283 1585
4742 149337 0 149337 4269
4300 149274 0 149274 1233
3587 178273 0 178273 3061
5096 74283 0 74283 1696
2567 96254 0 96254 1473
5096 74283 0 74283 1468
5096 74283 0 74283 1612
4300 149274 0 149274 1664
3938 147609 0 147609 1260
127511 1448 35530
0 137984 179117
130765 89886 119...

result:

wrong answer Integer 0 violates the range [1, 200000]

Test #6:

score: 0
Wrong Answer
time: 139ms
memory: 63860kb

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:

2935 67881 0 67881 1091
3151 153306 0 153306 2082
3815 14013 0 14013 765
2935 67881 0 67881 1628
2935 67881 0 67881 1064
2935 67881 0 67881 1545
3096 43474 0 43474 2344
2935 67881 0 67881 1465
2935 67881 0 67881 1548
2935 67881 0 67881 1521
103373 133610 186702
138116 166333 11082
191314 176954 1479...

result:

wrong answer Integer 0 violates the range [1, 200000]

Test #7:

score: 0
Time Limit Exceeded

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:


result:


Test #8:

score: 0
Wrong Answer
time: 195ms
memory: 77424kb

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:

5037 197169 0 197169 4251
5037 197169 0 197169 4527
5037 197169 0 197169 4802
5037 197169 0 197169 4948
5037 197169 0 197169 4442
5037 197169 0 197169 4913
5037 197169 0 197169 4457
5037 197169 0 197169 4375
5037 197169 0 197169 4355
5037 197169 0 197169 4682
5037 197169 0 197169 4678
5037 197169 0 ...

result:

wrong answer Integer 0 violates the range [1, 200000]

Test #9:

score: 0
Wrong Answer
time: 454ms
memory: 77292kb

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:

3342 153735 0 153735 2000
3089 68922 0 68922 1859
3089 68922 0 68922 1898
3342 153735 0 153735 2157
3342 153735 0 153735 1050
3089 68922 0 68922 1979
3342 153735 0 153735 1448
3342 153735 0 153735 1188
3342 153735 0 153735 1807
3342 153735 0 153735 1471
3342 153735 0 153735 2071
3342 153735 0 153735...

result:

wrong answer Integer 0 violates the range [1, 200000]

Test #10:

score: 0
Wrong Answer
time: 741ms
memory: 77284kb

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:

3713 88878 0 88878 1277
2714 95660 0 95660 834
2714 95660 0 95660 1383
2714 95660 0 95660 927
3694 19304 0 19304 1329
2714 95660 0 95660 718
3713 88878 0 88878 552
2714 95660 0 95660 940
3694 19304 0 19304 1133
3713 88878 0 88878 763
2714 95660 0 95660 1213
3694 19304 0 19304 1234
2714 95660 0 95660...

result:

wrong answer Integer 0 violates the range [1, 200000]