UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#196663#2676. MST+1tkswls1003467ms87192kbC++112.4kb2023-10-29 11:06:572023-10-29 12:03:12

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, q, f[200005], siz[200005], fa[200005][21], maxn[200005][21], nxt[400005], to[400005], head[200005], ccnt, w[400005], d[200005];
inline void add(int p, int q, int ww) {
//	cout << p << "!" << q << "!" << ww << "@\n";
	nxt[++ccnt] = head[p];
	w[ccnt] = ww;
	to[ccnt] = q;
	head[p] = ccnt;
}
struct node {
	int u, v, w;
} b[200005];
bool cmp(node p, node q) {
	return p.w < q.w;
}
inline int finds(int p) {
	return (f[p] == p) ? p : (f[p] = finds(f[p]));
}
inline void merge(int p, int q) {
	p = finds(p), q = finds(q);
	if (siz[p] > siz[q]) {
		siz[p] += siz[q];
		f[q] = p;
	} else {
		siz[q] += siz[p];
		f[p] = q;
	}
}
inline void dfs(int p, int q, int ww) {
	d[p] = d[q] + 1;
	fa[p][0] = q;
	maxn[p][0] = ww;
	for (int i = 1; i <= 20; i++) {
		fa[p][i] = fa[fa[p][i - 1]][i - 1];
		maxn[p][i] = max(maxn[p][i - 1], maxn[fa[p][i - 1]][i - 1]);
	}
	for (int i = head[p]; i; i = nxt[i]) {
		if (to[i] != q) {
			dfs(to[i], p, w[i]);
		}
	}
}
inline int solve(int p, int q) {
	int cnt = 0;
	if (p == q) return 0;
	if (d[p] < d[q]) swap(p, q);
	for (int i = 20; i >= 0; i--) {
		if (d[fa[p][i]] >= d[q]) {
			cnt = max(cnt, maxn[p][i]);
			p = fa[p][i];
		}
	}
	if (p == q) return cnt;
	for (int i = 20; i >= 0; i--) {
		if (fa[p][i] != fa[q][i]) {
			cnt = max(cnt, maxn[p][i]);
			cnt = max(cnt, maxn[q][i]);
			p = fa[p][i], q = fa[q][i];
		}
	}
	cnt = max(cnt, max(maxn[p][0], maxn[q][0]));
	return cnt;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		cin >> b[i].u >> b[i].v >> b[i].w;
	}
	for (int i = 1; i <= n; i++) {
		f[i] = i, siz[i] = i;
	}
	sort(b + 1, b + m + 1, cmp);
	for (int i = 1; i <= m; i++) {
		if (finds(b[i].u) != finds(b[i].v)) {
			merge(b[i].u, b[i].v);
			add(b[i].u, b[i].v, b[i].w);
			add(b[i].v, b[i].u, b[i].w);
		}
	}
	dfs(1, 0, 0);
	int u, v, w;
//	for (int i = 1; i <= n; i++) {
//		for (int j = 0; j <= 2; j++) {
//			cout << fa[i][j] << "|" << maxn[i][j] << "[][]";
//		}
//		cout << "\n";
//	}
	for (int i = 1; i <= q; i++) {
		cin >> u >> v >> w;
//		cout << solve(u, v) << "[]\n";
		if (solve(u, v) > w) {
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
	}
}
//7 10 1
//2 1 9878
//3 2 7815
//4 1 2790
//5 2 22774
//6 1 17006
//7 6 25666
//2 2 4770
//2 1 30079
//3 4 26311
//2 3 6079
//7 1 9242

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1396kb

input:

200 1000 1000
114 175 972887222
40 26 823283636
79 106 44662211
197 97 6260935
14 9 981337330
95 145...

output:

No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
Yes
No
Yes
...

result:

ok 1000 lines

Test #2:

score: 5
Accepted
time: 0ms
memory: 1392kb

input:

200 1000 1000
131 15 844092871
37 77 599020648
126 15 538348494
64 168 931023887
195 187 194611589
4...

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
Yes
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 1000 lines

Test #3:

score: 5
Accepted
time: 0ms
memory: 1392kb

input:

200 1000 1000
88 174 817926528
132 130 347818041
60 75 313998222
89 169 668639482
146 150 803111569
...

output:

No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No...

result:

ok 1000 lines

Test #4:

score: 5
Accepted
time: 0ms
memory: 1388kb

input:

200 1000 1000
197 88 603048624
33 48 284329610
148 73 583593992
157 121 591601533
1 33 811365597
145...

output:

Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
Ye...

result:

ok 1000 lines

Test #5:

score: 5
Accepted
time: 1ms
memory: 1392kb

input:

200 1000 1000
187 50 706413486
92 19 412566940
19 200 409720944
64 52 626046943
75 195 386886174
11 ...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
...

result:

ok 1000 lines

Test #6:

score: 5
Accepted
time: 0ms
memory: 1392kb

input:

200 1000 1000
167 188 462588134
199 166 140783785
50 159 907237032
68 20 831805450
130 4 633121568
1...

output:

No
Yes
No
Yes
No
Yes
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
Yes
No
Yes
Yes
No
No
No
Yes
No
Yes...

result:

ok 1000 lines

Test #7:

score: 5
Accepted
time: 0ms
memory: 1392kb

input:

200 1000 1000
67 78 573944416
49 158 293164901
149 166 222115551
79 7 201713000
110 183 249105127
33...

output:

No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Y...

result:

ok 1000 lines

Test #8:

score: 5
Accepted
time: 0ms
memory: 1392kb

input:

200 1000 1000
13 112 519171929
180 183 745759878
32 22 416430614
134 183 542239207
41 3 966263833
11...

output:

No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
...

result:

ok 1000 lines

Test #9:

score: 5
Accepted
time: 0ms
memory: 1388kb

input:

200 1000 1000
163 100 126177377
79 48 325196821
82 97 670906853
199 99 219391910
149 2 504810857
48 ...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
No...

result:

ok 1000 lines

Test #10:

score: 5
Accepted
time: 0ms
memory: 1392kb

input:

200 1000 1000
22 40 668494032
43 169 278056787
193 141 133192286
59 191 99205764
86 46 203784874
122...

output:

No
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
No
No
No
Yes
No
N...

result:

ok 1000 lines

Test #11:

score: 5
Accepted
time: 393ms
memory: 87184kb

input:

200000 200000 200000
115813 188050 178873569424184704
164797 75967 967675602502285241
68600 117155 9...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 200000 lines

Test #12:

score: 5
Accepted
time: 350ms
memory: 87188kb

input:

200000 200000 200000
165414 65183 656462071751070210
140205 151727 156144301717092257
166088 97867 7...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 200000 lines

Test #13:

score: 5
Accepted
time: 323ms
memory: 87184kb

input:

200000 200000 200000
83561 33291 723165511383302179
196281 96992 116190891694812781
89624 24791 6302...

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 200000 lines

Test #14:

score: 5
Accepted
time: 339ms
memory: 87192kb

input:

200000 200000 200000
177431 131248 825022268213794784
39333 23308 734690283699037773
44557 156852 30...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Y...

result:

ok 200000 lines

Test #15:

score: 5
Accepted
time: 341ms
memory: 87184kb

input:

200000 200000 200000
58080 100800 993305934962844366
125518 129137 368105932209799237
7609 66757 105...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Y...

result:

ok 200000 lines

Test #16:

score: 5
Accepted
time: 337ms
memory: 87188kb

input:

200000 200000 200000
46251 84476 298479658788035981
57420 113773 589029888604679364
42709 45727 9945...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Y...

result:

ok 200000 lines

Test #17:

score: 5
Accepted
time: 353ms
memory: 87192kb

input:

200000 200000 200000
140894 196540 993696966741788652
135317 118403 425027535236087729
163258 158217...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 200000 lines

Test #18:

score: 5
Accepted
time: 331ms
memory: 87188kb

input:

200000 200000 200000
78140 58702 824772058217121340
199760 130525 402065417829475932
46471 149221 38...

output:

Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Y...

result:

ok 200000 lines

Test #19:

score: 5
Accepted
time: 343ms
memory: 87184kb

input:

200000 200000 200000
125825 92178 371471400690081863
173849 74835 105756828037432194
183030 124251 3...

output:

Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes...

result:

ok 200000 lines

Test #20:

score: 5
Accepted
time: 356ms
memory: 87188kb

input:

200000 200000 200000
86978 60192 92468092067736231
115780 87286 520432024207853218
38563 19205 48451...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 200000 lines