Submission #125830

#TimeUsernameProblemLanguageResultExecution timeMemory
125830mechfrog88Valley (BOI19_valley)C++14
59 / 100
3031 ms25764 KiB
#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;
};

struct ed{
	ll u,v,w;
};

vector <vector<node>> graph;
vector <ll> euler;
vector <pair<ll,ll>> pos;
vector <ed> edge;
vector <ll> index1;

void dfs(ll p, ll v){
	pos[v].first = euler.size();
	index1[v] = euler.size();
	euler.push_back(v);
	for (int z=0;z<graph[v].size();z++){
		if (graph[v][z].point == p) continue;
		dfs(v,graph[v][z].point);
		euler.push_back(v);
	}
	pos[v].second = euler.size()-1;
}

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);
		ed ede;
		ede.u = a; ede.v = b; ede.w = temp.weight;
		edge.push_back(ede);
	}
	vector <bool> shops(n+1,false);
	for (int z=0;z<s;z++){
		ll temp;
		cin >> temp;
		shops[temp] = true;
	}
	pos.resize(n+1);
	index1.resize(n+1);
	dfs(0,1);
	if (s == n){
		for (int z=0;z<q;z++){
			ll k,t;
			cin >> k >> t;
			k--;
			ll l,r;
			ll s1 = pos[edge[k].u].second-pos[edge[k].u].first;
			ll s2 = pos[edge[k].v].second-pos[edge[k].v].first;
			if (s1 > s2){
				l = pos[edge[k].v].first;
				r = pos[edge[k].v].second;
			}
			else{
				l = pos[edge[k].u].first;
				r = pos[edge[k].u].second;
			}
			bool in1 = false;
			bool in2 = false;
			if (l <= index1[t] && index1[t] <= r){
				in1 = true;
			}
			if (l <= index1[e] && index1[e] <= r){
				in2 = true;
			}
			if (in1 ^ in2){
				cout << 0 << endl;
			} else {
				cout << "escaped" << endl; 
			}
		}
		return 0;
	}
	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 'void dfs(ll, ll)':
valley.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int z=0;z<graph[v].size();z++){
               ~^~~~~~~~~~~~~~~~
valley.cpp: In function 'int main()':
valley.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<graph[t].size();x++){
                ~^~~~~~~~~~~~~~~~
valley.cpp:123:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int x=0;x<graph[v].size();x++){
                 ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...