ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#196663 | #2676. MST+1 | tkswls | 100 | 3467ms | 87192kb | C++11 | 2.4kb | 2023-10-29 11:06:57 | 2023-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