oj.uz

Submission #498128

# Submission time Handle Problem Language Result Execution time Memory
498128 2021-12-24T12:10:50 Z AQ0212 Valley (BOI19_valley) C++17
36 / 100
 3000 ms 18176 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2700 KB Output is correct
2 Correct 41 ms 2840 KB Output is correct
3 Correct 39 ms 2720 KB Output is correct
4 Correct 49 ms 2740 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2700 KB Output is correct
2 Correct 41 ms 2840 KB Output is correct
3 Correct 39 ms 2720 KB Output is correct
4 Correct 49 ms 2740 KB Output is correct
5 Correct 133 ms 2928 KB Output is correct
6 Correct 69 ms 2804 KB Output is correct
7 Correct 102 ms 2784 KB Output is correct
8 Correct 128 ms 2816 KB Output is correct
9 Correct 130 ms 2796 KB Output is correct
10 Correct 160 ms 2784 KB Output is correct
11 Correct 40 ms 2824 KB Output is correct
12 Correct 114 ms 2816 KB Output is correct
13 Correct 109 ms 2796 KB Output is correct
14 Correct 212 ms 2704 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2700 KB Output is correct
2 Correct 41 ms 2840 KB Output is correct
3 Correct 39 ms 2720 KB Output is correct
4 Correct 49 ms 2740 KB Output is correct
5 Correct 133 ms 2928 KB Output is correct
6 Correct 69 ms 2804 KB Output is correct
7 Correct 102 ms 2784 KB Output is correct
8 Correct 128 ms 2816 KB Output is correct
9 Correct 130 ms 2796 KB Output is correct
10 Correct 160 ms 2784 KB Output is correct
11 Correct 40 ms 2824 KB Output is correct
12 Correct 114 ms 2816 KB Output is correct
13 Correct 109 ms 2796 KB Output is correct
14 Correct 212 ms 2704 KB Output is correct
15 Execution timed out 3075 ms 18176 KB Time limit exceeded
16 Halted 0 ms 0 KB -