Submission #153033

#	Time	Username	Problem	Language	Result	Execution time	Memory
153033		abacaba	Valley (BOI19_valley)	C++14	100 / 100	389 ms	40772 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;
const int L = 20;
int n, s, q, t, tin[N], tout[N], last, up[L][N];
ll minn[N], d[N], dp[L][N];
vector <int> g[N];
vector <edge> e;
bool is[N];

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

void build(int v, int p = t) {
	tin[v] = ++last;
	up[0][v] = p;
	for(int i = 1; i < L; ++i)
		up[i][v] = up[i-1][up[i-1][v]];
	if(is[v])
		minn[v] = d[v];
	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);
			minn[v] = min(minn[v], minn[to]);
		}
	}
	tout[v] = ++last;
}

void build_dp(int v, int p = t) {
	dp[0][v] = minn[v];
	for(int i = 1; i < L; ++i)
		dp[i][v] = min(dp[i-1][v], dp[i-1][up[i-1][v]]);
	for(int i : g[v]) {
		int to = (e[i].u == v ? e[i].v : e[i].u);
		if(to != p)
			build_dp(to, v);
	}
}

inline ll get_lowest(int a, int b) {
	ll res = inf;
	for(int i = L - 1; i >= 0; --i)
		if(upper(a, up[i][b])) {
			res = min(res, dp[i][b]);
			b = up[i][b];
		}
	return min(res, dp[0][b]);
}


int main() {
	fill(minn, minn + N, inf);
	for(int i = 0; i < L; ++i)
		fill(dp[i], dp[i] + 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);
    	is[x] = true;
    }
    build(t);
    for(int i = 1; i <= n; ++i) {
    	if(minn[i] != inf)
	    	minn[i] -= 2LL * d[i];
    }
    build_dp(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 = get_lowest(v, x);
    	if(val < inf)
	    	printf("%lld\n", val + d[x]);
	    else
	    	puts("oo");
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:97: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:100: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:107:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d", &x);
      ~~~~~^~~~~~~~~~
valley.cpp:118: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: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41