Submission #125675

#	Time	Username	Problem	Language	Result	Execution time	Memory
125675		mechfrog88	Valley (BOI19_valley)	C++14	36 / 100	3036 ms	14492 KiB

valley

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;

struct node{
	ll point;
	ll index;
	ll weight;
};

vector <vector<node>> graph;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,s,q,e;
	cin >> n >> s >> q >> e;
	graph.resize(n+1);
	for (int z=0;z<n-1;z++){
		node temp;
		ll a,b;
		cin >> a >> b >> temp.weight;
		temp.index = z+1;
		temp.point = b;
		graph[a].push_back(temp);
		temp.point = a;
		graph[b].push_back(temp);
	}
	vector <bool> shops(n+1,false);
	for (int z=0;z<s;z++){
		ll temp;
		cin >> temp;
		shops[temp] = true;
	}
	for (int z=0;z<q;z++){
		ll r,t;
		cin >> r >> t;
		vector <ll> distance(n+1,LLONG_MAX);
		queue <node> que;
		vector <bool> visited(n+1,false);
		visited[t] = true;
		distance[t] = 0;
		for (int x=0;x<graph[t].size();x++){
			if (graph[t][x].index == r) continue;
			if (visited[graph[t][x].point]) continue;
			distance[graph[t][x].point] = graph[t][x].weight; 
			que.push(graph[t][x]);
		}
		while (!que.empty()){
			node temp = que.front();
			ll v = temp.point;
			visited[v] = true;
			que.pop();
			for (int x=0;x<graph[v].size();x++){
				if (graph[v][x].index == r) continue;
				if (visited[graph[v][x].point]) continue;
				distance[graph[v][x].point] = distance[v]+graph[v][x].weight; 
				que.push(graph[v][x]);
			}
		}
		if (visited[e] == true){
			cout << "escaped" << endl;
		}
		else {
			ll mini = LLONG_MAX;
			for (int z=1;z<=n;z++){
				if (shops[z])
				mini = min(distance[z],mini);
			}
			if (mini == LLONG_MAX){
				cout << "oo" << endl;
			} else {
				cout << mini << endl;
			}
		}
	}
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<graph[t].size();x++){
                ~^~~~~~~~~~~~~~~~
valley.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int x=0;x<graph[v].size();x++){
                 ~^~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 0 / 23
• Subtask 4: 0 / 41