oj.uz

답안 #124560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124560 2019-07-03T13:52:07 Z groeneprof 관광 (NOI14_sightseeing) C++14
0 / 25
 3500 ms 104220 KB 
#include <bits/stdc++.h>
#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
// #define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
struct edge
{
	int u, v, q;
	bool operator< (edge other){
		return mp(q, mp(u, v)) < mp(other.q, mp(other.u, other.v));
	}
};
int V, E, Q;
vector<edge> edgelist;
vector<vector<pair<int, int> > > graph;
vector<int> uf, dist;
int root(int a){
	if(uf[a] == a) return a;
	return uf[a] = root(uf[a]);
}
void merge(int a, int b){
	a = root(a); b = root(b);
	if(rand()%2) swap(a, b);
	uf[a] = b;
}

void dfs(int u, int par, int d){
	dist[u] = d;
	for(auto e : graph[u]) if(e.first!=par){
		dfs(e.first, u, min(d,e.second));
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>V>>E>>Q;
	edgelist.resize(E);
	uf.resize(V);
	graph.resize(V);
	dist.resize(V);
	F(i,E){
		int a, b, q;
		cin>>a>>b>>q;
		edgelist[i] = {a-1, b-1, q};
	}
	sort(edgelist.begin(), edgelist.end());
	F(i,V) uf[i] = i;
	for(int i = E-1; i>=0; i--){
		H(i);
		edge e = edgelist[i];
		if(root(e.u)!=root(e.v)){
			merge(e.u, e.v);
			graph[e.u].push_back({e.v, e.q});
			graph[e.v].push_back({e.u, e.q});
		}
	}
	//dfs(0, -1, 0);
	int prev = 0;
	F(i, Q){
		int a;
		cin>>a;
		dist.assign(V, 0);
		dfs(prev, -1, 1e18);
		if(a-1 == prev){
			cout<<"0\n";
			continue;
		}
		prev = a-1;
		cout<<dist[a-1]<<"\n";
	}
	return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3542 ms 4804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3549 ms 104220 KB Time limit exceeded
2 Halted 0 ms 0 KB -