oj.uz

Submission #5277

# Submission time Handle Problem Language Result Execution time Memory
5277 2014-03-15T07:31:14 Z tncks0121 Sightseeing (NOI14_sightseeing) C++
25 / 25
 2748 ms 186032 KB 
#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_], L;

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 = lnk2[e]) {
			int v = con2[e], c = cst2[e];
			if(c >= w && !visited[v]) visited[v] = true, Res[v] = w, que[++qr] = v;
		}
	}
}

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;
		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];
			++L; lnk2[L] = start2[u]; start2[u] = L; con2[L] = v; cst2[L] = c;
			++L; lnk2[L] = start2[v]; start2[v] = L; con2[L] = u; cst2[L] = 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;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 185952 KB Output is correct
2 Correct 0 ms 185952 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 185952 KB Output is correct
2 Correct 0 ms 185952 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 185952 KB Output is correct
2 Correct 12 ms 185952 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1572 ms 185952 KB Output is correct
2 Correct 2748 ms 186032 KB Output is correct