| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 5273 | tncks0121 | Sightseeing (NOI14_sightseeing) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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], link[E_];
int start2[V_], link2[E_+E_], con2[E_+E_], cst2[E_+E_];
int que[V_], qf, qr;
bool visited[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 > 0; e = link2[e]) {
int v = con2[e], c = cst2[e];
if(c >= w && !visited[v]) visited[v] = true, Res[v] = w, que[++qr] = v;
}
}
}
int main() {
int i, j, k;
scanf("%d%d%d", &V, &E, &Q);
for(int i = 1; i <= E; i++) {
int u, v, c; scanf("%d%d%d", &u, &v, &c);
link[i] = start[c]; start[c] = i;
link2[i+i-1] = start2[u]; start2[u] = i+i-1; con2[i+i-1] = v; cst2[i+i-1] = c;
link2[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 = link[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;
}