Submission #153018

#	Time	Username	Problem	Language	Result	Execution time	Memory
153018		abacaba	Valley (BOI19_valley)	C++14	23 / 100	190 ms	13864 KiB

valley

#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <random>
#include <bitset>
#include <string>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <stack>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

struct edge {
	int u, v, w;
};

const ll inf = 2e18;
const int N = 1e5 + 15;
int n, s, q, t, tin[N], tout[N], last;
ll dp[N], d[N];
vector <int> g[N];
vector <edge> e;

inline bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void build(int v, int p = -1) {
	tin[v] = ++last;
	for(int i : g[v]) {
		int to = (e[i].u == v ? e[i].v : e[i].u), w = e[i].w;
		if(to != p) {
			d[to] = d[v] + w;
			build(to, v);
			dp[v] = min(dp[v], dp[to] + w);
		}
	}
	tout[v] = ++last;
}

int main() {
	fill(dp, dp + N, inf);
    scanf("%d%d%d%d", &n, &s, &q, &t);
    for(int i = 1; i < n; ++i) {
    	int u, v, w;
    	scanf("%d%d%d", &u, &v, &w);
    	e.pb({u, v, w});
    	g[u].pb(e.size() - 1);
    	g[v].pb(e.size() - 1);
    }
    for(int i = 1; i <= s; ++i) {
    	int x;
    	scanf("%d", &x);
    	dp[x] = 0;
    }
    build(t);
    while(q--) {
    	int i, x;
    	scanf("%d%d", &i, &x);
    	int u = e[i - 1].u, v = e[i - 1].v;
    	if(tin[u] > tin[v])
    		swap(u, v);
    	if(!upper(v, x)) {
    		puts("escaped");
    		continue;
    	}
    	ll val = min(dp[x], dp[v] + d[x] - d[v]);
    	if(val < inf)
	    	printf("%lld\n", val);
	    else
	    	puts("oo");
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &s, &q, &t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:69:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d%d", &u, &v, &w);
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:76:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &x);
      ~~~~~^~~~~~~~~~
valley.cpp:82:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d", &i, &x);
      ~~~~~^~~~~~~~~~~~~~~~

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