제출 #321661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
321661		vkgainz	Valley (BOI19_valley)	C++17	100 / 100	314 ms	56940 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define ll long long
const int MX = 1e5+5;
vector<pair<int, int>> adj[MX];
vector<pair<int, int>> edge(MX);
bool shop[MX];
ll subdist[MX];
ll dpdist[MX][20], tabdist[MX][20];
int parent[MX][20];
int sz[MX], st[MX], depth[MX];
int t, e;
void dfs(int curr, int par) {
    //make sure everything counted
    if(shop[curr]) subdist[curr] = 0LL;
    ++sz[curr];
    st[curr] = t++;
    for(auto &next : adj[curr]) if(next.f!=par) {
        tabdist[next.f][0] = next.s*1LL;
        parent[next.f][0] = curr;
        depth[next.f] = depth[curr]+1;
        dfs(next.f,curr);
        subdist[curr] = min(subdist[curr], subdist[next.f]+next.s*1LL);
        sz[curr]+=sz[next.f];
    }
}
//check for overflow!
void query(int p, int r) {
    //check if parent
    if(st[r]<st[p] || st[r]>=st[p]+sz[p]) { //??
        cout << "escaped" << "\n";
        return;
    }
    ll ret = subdist[r];
    ll distAdd = 0;
    for(int bit=20;bit>=0;bit--) {
        if(depth[r]-(1<<bit)>=depth[p]) {
            ret = min(ret, distAdd+dpdist[r][bit]);
            distAdd+=tabdist[r][bit];
            r = parent[r][bit];
        }
    }
    if(ret>=1e16) cout << "oo" << "\n";
    else cout << ret << "\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,s,q;
    cin >> n >> s >> q >> e;
    --e;
    for(int i=0;i<n-1;i++) {
        cin >> edge[i].f >> edge[i].s;
        --edge[i].f, --edge[i].s;
        int w; cin >> w;
        adj[edge[i].f].push_back({edge[i].s,w});
        adj[edge[i].s].push_back({edge[i].f,w});
    }
    for(int i=0;i<s;i++) {
        int c; cin >> c;
        shop[--c] = 1;
    }
    for(int i=0;i<n;i++) {
        subdist[i] = 1e16;
        for(int j=0;j<20;j++) tabdist[i][j] = 1e16;
    }
    dfs(e,-1);
    for(int j=0;j<20;j++) {
        for(int i=0;i<n;i++) {
            if(j==0) {
                dpdist[i][j] = min(tabdist[i][j]+subdist[parent[i][j]],subdist[i]);               
            }
            else {
                //check these
                parent[i][j] = parent[ parent[i][j-1] ][j-1];
                tabdist[i][j] = tabdist[i][j-1] + tabdist[ parent[i][j-1] ][j-1];
                dpdist[i][j] = min(dpdist[i][j-1], tabdist[i][j-1]+dpdist[ parent[i][j-1] ][j-1]);
            }
        }
    }
    while(q--) {
        int i,r; cin >> i >> r;
        --i, --r;
        int a = edge[i].f, b = edge[i].s;
        if(depth[a]<depth[b]) swap(a,b);
        query(a, r);
    }
}

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