Submission #496359

#	Time	Username	Problem	Language	Result	Execution time	Memory
496359		Nuraly_Serikbay	Valley (BOI19_valley)	C++14	0 / 100	34 ms	47924 KiB

valley

/*	Speech to the young  */

#include <bits/stdc++.h>
 
#define endl "\n"
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define sz size()
#define rep(i,k,n) for(int i = k ; i <= n ; ++i)
#define per(i,k,n) for(int i = k ; i >= n ; --i)
#define Zymraq() ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define all(x) x.begin(),x.end()
#define fr(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define toqta return 0
#define PERMUTE next_permutation
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;

 
using namespace std;
  
typedef long long ull;
typedef unsigned long long ll;
typedef string S;
typedef double D;
  
const int N = 1e6 + 17;
const int modd = 1e9 + 7;
const int INF = 2e9 - 19;
const int P = 37;
const ll NN = 1e7 + 17;
const D eps = 1e-19;
const double pi = 3.141592653589793238462643383279 ;
  
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b){
    return (a.second < b.second);
}

void pre (ll a) {
    cout << fixed << setprecision(a);
    return;
} 

ll n, s, q, e;
vector <ll> g[N];
ll dist[200][200];
bool sp[N];
ll broke[200][200];
vector <pair <ll, ll>> rd;
bool ok;
ll d[200];

void dfs (ll v, ll pr) {
	if (v == e) {
		ok = 1;
		return;
	}
	if (ok) return;
	for (auto to: g[v]) {
		if (broke[v][to] == 0 && to != pr) {
			d[to] = d[v] + dist[v][to];
			dfs (to, v);
		}
	}
	return;
}

int main(){
	cin >> n >> s >> q >> e;
	for (int i = 1; i < n; ++ i) {
		ll x, y, dst;
		cin >> x >> y >> dst;
		g[x].pb (y);
		g[y].pb (x);
		dist[x][y] = dst;
		dist[y][x] = dst;	
		rd.pb (mp (x, y));
	}
	for (int i = 1; i <= s; ++ i) {
		ll x;
		cin >> x;
		sp[x] = 1;
	}
	while (q --) {
		ll l, r, ans = INF;
		cin >> l >> r;
		broke[rd[l - 1].F][rd[l - 1].S] = 1;
		broke[rd[l - 1].S][rd[l - 1].F] = 1;
		ok = 0;
		for (int i = 1; i <= n; ++ i) d[i] = 0;
		if (sp[r] == 1) ans = 0;
		dfs (r, -1); 					
		broke[rd[l - 1].F][rd[l - 1].S] = 0;
		broke[rd[l - 1].S][rd[l - 1].F] = 0;
		if (ok == 1) {
			cout << "escaped\n";
			continue;
		}
		for (int i = 1; i <= n; ++ i) {
			if (sp[i] && d[i] != 0) ans = min (ans, d[i]);
		}
		if (ans == INF) {
			cout << "oo\n";
			continue;
		}
		cout << ans << '\n';
	}
	return 0;
}

/*
3 3 2 1
1 2 1
1 3 1
1 2 3
2 2 
3 1

*/

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 1; i < n; ++ i) {
      |                  ~~^~~
valley.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   81 |  for (int i = 1; i <= s; ++ i) {
      |                  ~~^~~~
valley.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
   92 |   for (int i = 1; i <= n; ++ i) d[i] = 0;
      |                   ~~^~~~
valley.cpp:101:21: warning: comparison of integer expressions of different signedness: 'int' and 'll' {aka 'long long unsigned int'} [-Wsign-compare]
  101 |   for (int i = 1; i <= n; ++ i) {
      |                   ~~^~~~

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