Submission #498126

#	Time	Username	Problem	Language	Result	Execution time	Memory
498126		AQ0212	Valley (BOI19_valley)	C++17	36 / 100	3029 ms	18448 KiB

valley

#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#include <bitset>

// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse,-fgcse-lm")
// #pragma GCC optimize("-ftree-pre,-ftree-vrp")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#define ll long long int
#define pb push_back
#define pll pair < ll , ll >
#define fi first
#define se second
#define all(x) x.begin(), x.end()

using namespace std;
 
// struct graphs{
// 	ll e, w, id;
// };

ll inf2 = 3e18;

ll ans, n, s, q, e;
vector < pll > g[ 100111 ];
vector < ll > markets;
map < pll , ll > mp;
 
int main (){
	ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

	// ll n, s, q, e;

	cin >> n >> s >> q >> e;

	for(int i = 1; i < n; i ++){
		ll u, v, w;

		cin >> u >> v >> w;

		g[ u ].pb(make_pair(v, w));
		g[ v ].pb(make_pair(u, w));

		mp[ make_pair(max(u, v), min(u, v)) ] = i;
	}

	for(int i = 1; i <= s; i ++){
		ll id;

		cin >> id;

		markets.pb(id);
	}

	while(q --){
		ll ch = 0, k, r;

		cin >> k >> r;

		vector < ll > dis(n + 1, inf2), parent(n + 1);
		dis[ r ] = 0;
		set < pll > q;
		q.insert(make_pair(dis[ r ], r));

		while(!q.empty()){
			ll v = q.begin()->second;
			q.erase(q.begin());
			if(v == e){
				cout << "escaped\n";
				ch ++;
				break;
			}

			for(int j = 0; j < g[ v ].size(); j ++){
				ll to = g[ v ][ j ].fi;
				ll len = g[ v ][ j ].se;

				if(dis[ v ] + len < dis[ to ] && mp[ make_pair(max(to, v), min(to, v)) ] != k){
					q.erase(make_pair(dis[ to ], to));
					dis[ to ] = dis[ v ] + len;
					parent[ to ] = v;
					q.insert(make_pair(dis[ to ], to));
				}
			}
		}

		if(!ch){
			ll ans = inf2;
			for(auto it : markets){
				ans = min(ans, ((ll)dis[ it ]));
			}

			if(ans != inf2){
				cout << ans << "\n";
			}else
				cout << "oo\n";
		}
	}


}
 
/*
 
5 2 3 1
1 2 3
1 3 2
3 4 1
3 5 2
2
4
2 2
2 5
4 5

*/

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |    for(int j = 0; j < g[ v ].size(); j ++){
      |                   ~~^~~~~~~~~~~~~~~

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