Submission #486511

#	Time	Username	Problem	Language	Result	Execution time	Memory
486511		Yazan_Alattar	Valley (BOI19_valley)	C++14	100 / 100	298 ms	67496 KiB

valley

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

priority_queue < pair <ll,ll> > q;
vector < pair <ll,ll> > adj[M];
int n, s, qry, root, in[M], out[M], timer, v[M], u[M], dep[M];
ll dist[M][20], mn[M][20], anc[M][20], cost[M];
bool shop[M];

void dfs(int node, int p)
{
    cost[node] = (shop[node] ? 0 : 1e18);
    in[node] = ++timer;
    for(auto i : adj[node]){
        if(i.F == p) continue;
        dep[i.F] = dep[node] + 1;
        anc[i.F][0] = node;
        dist[i.F][0] = i.S;
        for(int j = 1; j < 20; ++j){
            anc[i.F][j] = anc[anc[i.F][j - 1]][j - 1];
            dist[i.F][j] = dist[i.F][j - 1] + dist[anc[i.F][j - 1]][j - 1];
        }
        dfs(i.F, node);
        cost[node] = min(cost[node], cost[i.F] + i.S);
    }
    out[node] = ++timer;
    return;
}

void dfs2(int node, int p)
{
    for(auto i : adj[node]){
        if(i.F == p) continue;
        mn[i.F][0] = i.S + cost[node];
        for(int j = 1; j < 20; ++j) if(anc[i.F][j]) mn[i.F][j] = min(mn[i.F][j - 1], mn[anc[i.F][j - 1]][j - 1] + dist[i.F][j - 1]);
        dfs2(i.F, node);
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> s >> qry >> root;
    for(int i = 1; i < n; ++i){
        ll w;
        cin >> v[i] >> u[i] >> w;
        adj[v[i]].pb({u[i], w});
        adj[u[i]].pb({v[i], w});
    }
    for(int i = 1; i <= s; ++i){
        int x;
        cin >> x;
        shop[x] = 1;
    }
    dfs(root, 0);
    dfs2(root, 0);
    int cnt = 1;
    while(qry--){
        int x, node;
        cin >> x >> node;
        int p = v[x];
        if(anc[u[x]][0] == v[x]) p = u[x];
        if(in[node] < in[p] || in[node] > out[p]) cout << "escaped\n";
        else{
            ll ans = cost[node], road = 0;
            for(int j = 19; j >= 0; --j){
                if(dep[anc[node][j]] < dep[p]) continue;
                ans = min(ans, mn[node][j] + road);
                road += dist[node][j];
                node = anc[node][j];
            }
            if(ans == 1e18) cout << "oo\n";
            else cout << ans << endl;
        }
    }
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:80:9: warning: unused variable 'cnt' [-Wunused-variable]
   80 |     int cnt = 1;
      |         ^~~

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