oj.uz

Submission #633181

# Submission time Handle Problem Language Result Execution time Memory
633181 2022-08-21T19:16:55 Z Alma Valley (BOI19_valley) C++17
36 / 100
 3000 ms 9816 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
using ll = long long;
using ii = pair<int,int>;

const int INF = 1e9;
const ll LLINF = 1e18;
using vi = vector<int>;
using vvi = vector<vi>;

void setIO (string fileName) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    if (fileName != "std") {
        freopen((fileName + ".in").c_str(), "r", stdin);
        freopen((fileName + ".out").c_str(), "w", stdout);
    }
}

struct edge {
	int a, b, c;
};

vector<ll> dijkstra (int n, int s, vector<vector<ii>>& adj) {
	vector<ll> dist(n, LLINF);
	dist[s] = 0;
	priority_queue<pair<ll, int>> pq;
	pq.push({0, s});

	while (!pq.empty()) {
		int u = pq.top().second;
		ll d = -pq.top().first;
		pq.pop();
		if (d > dist[u]) continue;
		for (ii p: adj[u]) {
			int v = p.fi, c = p.se;
			if (d + c < dist[v]) {
				dist[v] = d+c;
				pq.push({-d-c, v});
			}
		}
	}
	return dist;
}

int main() {
    setIO("std");

    int n, s, q, e;
	cin >> n >> s >> q >> e;
	e--;
	vector<edge> list(n-1);
	for (int i = 0; i < n-1; i++) {
		cin >> list[i].a >> list[i].b >> list[i].c;
		list[i].a--;
		list[i].b--;
	}
	int x, y;
	vector<bool> shop(n, false);
	for (int i = 0; i < s; i++) {
		cin >> x;
		shop[x-1] = true;
	}
	while (q--) {
		cin >> x >> y;
		x--; y--;
		vector<vector<ii>> adj(n);
		for (int i = 0; i < n-1; i++) {
			if (i == x) continue;
			adj[list[i].a].push_back({list[i].b, list[i].c});
			adj[list[i].b].push_back({list[i].a, list[i].c});
		}
		vector<ll> dist = dijkstra(n, y, adj);
		if (dist[e] != LLINF) {
			cout << "escaped\n";
		} else {
			ll ans = LLINF;
			for (int i = 0; i < n; i++) {
				if (shop[i] and dist[i] != LLINF) {
					ans = min(ans, dist[i]);
				}
			}
			if (ans == LLINF) cout << "oo\n";
			else cout << ans << '\n';
		}
	}

    return 0;
}

Compilation message

valley.cpp: In function 'void setIO(std::string)':
valley.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen((fileName + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((fileName + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 340 KB Output is correct
2 Correct 105 ms 356 KB Output is correct
3 Correct 105 ms 348 KB Output is correct
4 Correct 106 ms 360 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 340 KB Output is correct
2 Correct 105 ms 356 KB Output is correct
3 Correct 105 ms 348 KB Output is correct
4 Correct 106 ms 360 KB Output is correct
5 Correct 139 ms 412 KB Output is correct
6 Correct 142 ms 400 KB Output is correct
7 Correct 130 ms 392 KB Output is correct
8 Correct 132 ms 408 KB Output is correct
9 Correct 143 ms 404 KB Output is correct
10 Correct 137 ms 392 KB Output is correct
11 Correct 128 ms 420 KB Output is correct
12 Correct 133 ms 388 KB Output is correct
13 Correct 129 ms 392 KB Output is correct
14 Correct 182 ms 404 KB Output is correct

Subtask #3
0 / 23.0

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

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 340 KB Output is correct
2 Correct 105 ms 356 KB Output is correct
3 Correct 105 ms 348 KB Output is correct
4 Correct 106 ms 360 KB Output is correct
5 Correct 139 ms 412 KB Output is correct
6 Correct 142 ms 400 KB Output is correct
7 Correct 130 ms 392 KB Output is correct
8 Correct 132 ms 408 KB Output is correct
9 Correct 143 ms 404 KB Output is correct
10 Correct 137 ms 392 KB Output is correct
11 Correct 128 ms 420 KB Output is correct
12 Correct 133 ms 388 KB Output is correct
13 Correct 129 ms 392 KB Output is correct
14 Correct 182 ms 404 KB Output is correct
15 Execution timed out 3097 ms 9816 KB Time limit exceeded
16 Halted 0 ms 0 KB -