oj.uz

Submission #512369

# Submission time Handle Problem Language Result Execution time Memory
512369 2022-01-16T09:59:51 Z MurotY Valley (BOI19_valley) C++14
0 / 100
 3000 ms 37852 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(r, 0, l);
		if (u[e]){
		     cout <<"escaped\n";
			fill(u, u+n+1, 0);
		} 
		else {
			queue <ll> q;
			vector <ll> dc(n+1, 1e9);
			for (int i=1;i<=s;i++) {
				if (u[b[i]]) q.push(b[i]), dc[b[i]]=0;
			}
			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);
					}
				}
		     }
			if (dc[r] == 1e9) cout << "oo\n";
			else	cout << dc[r] <<"\n";
			fill(u, u+n+1, 0);
		}
	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 23860 KB Output is correct
2 Incorrect 34 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 23860 KB Output is correct
2 Incorrect 34 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3089 ms 37852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 23860 KB Output is correct
2 Incorrect 34 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -