Submission #661231

#	Time	Username	Problem	Language	Result	Execution time	Memory
661231		jiahng	Valley (BOI19_valley)	C++14	59 / 100	3050 ms	28396 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];
void dfs(int x, int p){
    st[x] = co++;
    aFOR(i, adj[x]) if (i.f != p){
        depth[i.f] = depth[x] + 1;
        dfs(i.f,x);
    }
    en[x] = co - 1;
}

vpi queries[maxn];
int ans[maxn];
vi C[maxn];
int dist[maxn];

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[depth[i]].pb(i);

    priority_queue <pi, vector <pi>, greater <pi> > pq, pq2;
    mem(dist, -1);
    DEC(i,N-1,0){
        while (!pq2.empty()){
            pq.push(pq2.top()); pq2.pop();
        }
        aFOR(j, C[i]){
            if (shop[j]){
                dist[j] = 0; pq.push(pi(0, j));
            }
        }

        while (!pq.empty()){
            pi cur = pq.top(); pq.pop();
            if (cur.f != dist[cur.s]) continue;
            if (depth[cur.s] == i-1){
                pq2.push(cur); continue;
            }

            aFOR(j, adj[cur.s]) if (dist[j.f] == -1 || dist[j.f] > cur.f + j.s){
                dist[j.f] = cur.f + j.s;
                pq.push(pi(dist[j.f], j.f)); 
            }
        }
        aFOR(j, C[i]){
            aFOR(k, queries[j]){
                ans[k.s] = dist[k.f];
            }
        }
    }


    FOR(i,1,Q){
        if (ans[i] == -2) cout << "escaped\n";
        else if (ans[i] == -1) cout << "oo\n";
        else cout << ans[i] << '\n';
    }
}

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