Submission #661232

#	Time	Username	Problem	Language	Result	Execution time	Memory
661232		jiahng	Valley (BOI19_valley)	C++14	100 / 100	313 ms	35328 KiB

valley

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 100010
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;


int N,S,Q,E,I,R;
int A[maxn], B[maxn], W[maxn], x;
bool shop[maxn];
vpi adj[maxn];

int co = 0;
int st[maxn], en[maxn], depth[maxn],sz[maxn];
int dp[maxn]; // min dist to go downwards from x to a shop
void dfs(int x, int p){
    st[x] = co++;
    sz[x] = 1;
    if (shop[x]) dp[x] = 0;
    else dp[x] = INF;
    aFOR(i, adj[x]) if (i.f != p){
        depth[i.f] = depth[x] + i.s;
        dfs(i.f,x);
        sz[x] += sz[i.f];
        dp[x] = min(dp[x], dp[i.f] + i.s);
    }
    en[x] = co - 1;
}
namespace UFDS{
    int p[maxn];
    int fl(int x){
        if (p[x] == x) return x;
        return p[x] = fl(p[x]);
    }
}
vpi queries[maxn];
int ans[maxn];
int C[maxn];
int dist[maxn], D[maxn];
priority_queue <pi> pq[maxn];

void dfs2(int x,int p){
    int mx = -1;
    aFOR(i, adj[x]) if (i.f != p){
        dfs2(i.f, x);
        if (mx == -1 || pq[mx].size() < pq[i.f].size()) mx = i.f;
    }

    if (mx != -1) pq[mx].swap(pq[x]);
    pq[x].push(pi(C[x], x));
    aFOR(i,adj[x]) if (i.f != p && i.f != mx){
        while (!pq[i.f].empty()){
            pq[x].push(pq[i.f].top()); pq[i.f].pop();
        }
    }
    vi v;
    while (!pq[x].empty() && pq[x].top().f >= C[x]){
        v.pb(pq[x].top().s); pq[x].pop();
    }
    FOR(i,1,(int)v.size()-1){
        int x = UFDS::fl(v[i]);
        UFDS::p[x] = UFDS::fl(v[0]);
    }
    if (!v.empty()){
        D[UFDS::fl(v[0])] = C[x]; pq[x].push(pi(C[x], UFDS::fl(v[0])));
    }
    aFOR(i, queries[x]){
        ans[i.s] = D[UFDS::fl(i.f)] + depth[i.f];
    }
}
int32_t main(){
    cin >> N >> S >> Q >> E;
    FOR(i,1,N-1){
        cin >> A[i] >> B[i] >> W[i];
        adj[A[i]].pb(pi(B[i], W[i]));
        adj[B[i]].pb(pi(A[i], W[i]));
    }

    FOR(i,1,S){
        cin >> x; shop[x] = 1;
    }
    dfs(E,-1);
    FOR(i,1,N-1){
        if (depth[A[i]] > depth[B[i]]) swap(A[i], B[i]); // A is the parent
    }
    FOR(i,1,Q){
        cin >> I >> R;
        if (!(st[B[I]] <= st[R] && st[R] <= en[B[I]])) ans[i] = -2;
        else{
            queries[B[I]].pb(pi(R, i));
        }
    }
    
    FOR(i,1,N) C[i] = dp[i] - depth[i]; // defn of C
    FOR(i,1,N) UFDS::p[i] = i;
    dfs2(E,-1);
    FOR(i,1,Q){
        if (ans[i] == -2) cout << "escaped\n";
        else if (ans[i] >= INF) cout << "oo\n";
        else cout << ans[i] << '\n';
    }
}

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