oj.uz

Submission #5272

# Submission time Handle Problem Language Result Execution time Memory
5272 2014-03-15T07:07:26 Z tncks0121 Sightseeing (NOI14_sightseeing) C++
15 / 25
 3364 ms 262144 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;

int V, E, Q;

struct edge {
	int v, c;
	edge (int v = 0, int c = 0): v(v), c(c) { }
	bool operator< (const edge &e) const { return c > e.c; }
	bool operator> (const edge &e) const { return c < e.c; }
};

vector<edge> Gph[E_];
int group[V_];
int Res[V_];

int get_group (int u) {
	return (u == group[u]) ? u : (group[u] = get_group(group[u]));
}

const int INF = 250005;
bool visited[V_];

vector<pii> Edges[INF];

void mark (int s, int c) {
	queue<int> que;
	que.push(s);
	while(!que.empty()) {
		int u = que.front(); que.pop();
		Res[u] = c; visited[u] = true;
		for(int i = 0; i < Gph[u].size(); i++) {
			edge &e = Gph[u][i];
			if(e.c >= c && !visited[e.v]) visited[e.v] = true, Res[e.v] = c, que.push(e.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);
		Gph[u].push_back (edge(v, c));
		Gph[v].push_back (edge(u, c));
		Edges[c].push_back( pii(u, v) );
	}

	if(E <=	100000) {
		priority_queue<edge, vector<edge>, greater<edge> > PQ;

		PQ.push(edge(1, 200005));
		for(int i = 2; i <= V; i++) Res[i] = -1;

		while(!PQ.empty()) {
			edge s = PQ.top(); PQ.pop();
			if(visited[s.v]) continue;
			visited[s.v] = true;
			for(int j = 0; j < Gph[s.v].size(); j++) {
				edge &e = Gph[s.v][j];
				int c = min(e.c, s.c);
				if(c > Res[e.v]) Res[e.v] = c, PQ.push(edge(e.v, c));
			}
		}
	}else {
		for(int i = 1; i <= V; i++) group[i] = i;

		for(int c = 200000; c >= 1; c--) {
			for(int i = 0; i < Edges[c].size(); i++) {
				int u = Edges[c][i].first, v = Edges[c][i].second;
				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 20 ms 128684 KB Output is correct
2 Correct 24 ms 128684 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 128816 KB Output is correct
2 Correct 28 ms 128684 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 131740 KB Output is correct
2 Correct 88 ms 131228 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3364 ms 248012 KB Output is correct
2 Memory limit exceeded 3296 ms 262144 KB Memory limit exceeded