oj.uz

답안 #511202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
511202 2022-01-15T12:28:45 Z MurotY Valley (BOI19_valley) C++14
0 / 100
 3000 ms 40748 KB 
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long 
#define ff first
#define ss second
using namespace std;
const int N=1e6+7;
vector <pair <ll,ll>> g[N];
ll a[N], b[N];
bool u[N];
void dfs(ll v, ll p, ll l){
	u[v]=1;
	for (auto it:g[v]){
		if (it.ff != p && it.ss != l){
			dfs(it.ff, v, l);
		}
	}
	return ;
}
int main()
{
	ll n, s, q, e;
	cin >> n >> s >> q >> e;
	
	for (int i=1;i<n;i++){
		int x, y;
		cin >> x >> y >> a[i];
		g[x].push_back({y, i});
		g[y].push_back({x, i});
	}
	map <ll,ll> mp;
	for (int i=1;i<=s;i++) cin >> b[i], mp[b[i]]++;
	while (q--){
		int l, r;
		cin >> l >> r;
		dfs(1, 0, l);
		if (u[r] && u[e]){
		     cout <<"escaped\n";
			fill(u, u+n+1, 0);
		} 
		else {
			queue <ll> q;
			vector <ll> dc(n+1, 1e9);
			dc[r]=0;
			q.push(r);
			while (!q.empty()){
				int x=q.front();
				q.pop();
				for (auto l:g[x]){
					if (dc[l.ff] >= dc[x]+a[l.ss]){
						dc[l.ff]=dc[x]+a[l.ss];
						q.push(l.ff);
					}
				}
			}
			ll ans=1e9;
			for (int i=1;i<=n;i++){
				if (mp[i] and u[r] == u[i]) ans=min(ans, dc[i]);
			}
			if (ans == 1e9) cout << "oo";
			else	cout << ans <<"\n";
			fill(u, u+n+1, 0);
		}
	}
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 41.0

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