#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int E_ = 5000005;
const int V_ = 500005;
const int LM = 200005;
int V, E, Q;
int group[V_];
int Res[V_];
int get_group (int u) {
return (u == group[u]) ? u : (group[u] = get_group(group[u]));
}
int edge[E_][2];
int start[LM], lnk[E_];
int start2[V_], lnk2[E_+E_], con2[E_+E_], cst2[E_+E_];
int que[V_], qf, qr;
bool visited[V_];
int last[V_];
void mark (int s, int w) {
qf = qr = 0; que[++qr] = s;
while(qf < qr) {
int u = que[++qf];
visited[u] = true; Res[u] = w;
for(int e = start2[u]; e > last[u]; e = lnk2[e]) {
int v = con2[e], c = cst2[e];
if(c >= w && !visited[v]) visited[v] = true, Res[v] = w, que[++qr] = v;
}
last[u] = start2[u];
}
}
int getint() {
int ret = 0;
while(1) {
char c = getchar();
if(c == 0) break;
if('0' <= c && c <= '9') { ret = c - '0'; break; }
}
while(1) {
char c = getchar();
if('0' <= c && c <= '9') ret = ret * 10 + c - '0';
else break;
}
return ret;
}
int main() {
scanf("%d%d%d\n", &V, &E, &Q);
for(int i = 1; i <= E; i++) {
int u = getint(), v = getint(), c = getint();
lnk[i] = start[c]; start[c] = i;
lnk2[i+i-1] = start2[u]; start2[u] = i+i-1; con2[i+i-1] = v; cst2[i+i-1] = c;
lnk2[i+i] = start2[v]; start2[v] = i+i; con2[i+i] = u; cst2[i+i] = c;
edge[i][0] = u; edge[i][1] = v;
}
for(int i = 1; i <= V; i++) group[i] = i;
for(int c = 200000; c >= 1; c--) {
for(int e = start[c]; e > 0; e = lnk[e]) {
int u = edge[e][0], v = edge[e][1];
int ug = get_group(u), vg = get_group(v), hg = get_group(1);
if(ug != vg) {
if(ug == hg) mark(v, c);
if(vg == hg) mark(u, c);
group[ug] = vg;
}
}
}
for(int i = 1; i <= Q; i++) {
int x; scanf("%d", &x);
printf("%d\n", Res[x]);
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
187904 KB |
Output is correct |
2 |
Correct |
0 ms |
187904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
187904 KB |
Output is correct |
2 |
Correct |
0 ms |
187904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
187904 KB |
Output is correct |
2 |
Correct |
20 ms |
187904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2788 ms |
187904 KB |
Output is correct |
2 |
Execution timed out |
3500 ms |
187976 KB |
Program timed out |