oj.uz

답안 #321661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321661 2020-11-13T01:39:21 Z vkgainz Valley (BOI19_valley) C++17
100 / 100
 314 ms 56940 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3692 KB Output is correct
2 Correct 5 ms 3692 KB Output is correct
3 Correct 5 ms 3692 KB Output is correct
4 Correct 5 ms 3692 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3692 KB Output is correct
2 Correct 5 ms 3692 KB Output is correct
3 Correct 5 ms 3692 KB Output is correct
4 Correct 5 ms 3692 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 4 ms 3948 KB Output is correct
7 Correct 4 ms 4076 KB Output is correct
8 Correct 4 ms 3968 KB Output is correct
9 Correct 4 ms 3960 KB Output is correct
10 Correct 4 ms 4076 KB Output is correct
11 Correct 4 ms 3948 KB Output is correct
12 Correct 4 ms 3948 KB Output is correct
13 Correct 4 ms 3948 KB Output is correct
14 Correct 4 ms 4076 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 53356 KB Output is correct
2 Correct 225 ms 52716 KB Output is correct
3 Correct 243 ms 52716 KB Output is correct
4 Correct 278 ms 54508 KB Output is correct
5 Correct 255 ms 54764 KB Output is correct
6 Correct 314 ms 56452 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3692 KB Output is correct
2 Correct 5 ms 3692 KB Output is correct
3 Correct 5 ms 3692 KB Output is correct
4 Correct 5 ms 3692 KB Output is correct
5 Correct 4 ms 3948 KB Output is correct
6 Correct 4 ms 3948 KB Output is correct
7 Correct 4 ms 4076 KB Output is correct
8 Correct 4 ms 3968 KB Output is correct
9 Correct 4 ms 3960 KB Output is correct
10 Correct 4 ms 4076 KB Output is correct
11 Correct 4 ms 3948 KB Output is correct
12 Correct 4 ms 3948 KB Output is correct
13 Correct 4 ms 3948 KB Output is correct
14 Correct 4 ms 4076 KB Output is correct
15 Correct 206 ms 53356 KB Output is correct
16 Correct 225 ms 52716 KB Output is correct
17 Correct 243 ms 52716 KB Output is correct
18 Correct 278 ms 54508 KB Output is correct
19 Correct 255 ms 54764 KB Output is correct
20 Correct 314 ms 56452 KB Output is correct
21 Correct 193 ms 52588 KB Output is correct
22 Correct 212 ms 52204 KB Output is correct
23 Correct 225 ms 52076 KB Output is correct
24 Correct 267 ms 54124 KB Output is correct
25 Correct 268 ms 56940 KB Output is correct
26 Correct 196 ms 52588 KB Output is correct
27 Correct 210 ms 52204 KB Output is correct
28 Correct 227 ms 52224 KB Output is correct
29 Correct 250 ms 53612 KB Output is correct
30 Correct 285 ms 55024 KB Output is correct
31 Correct 202 ms 52788 KB Output is correct
32 Correct 211 ms 52332 KB Output is correct
33 Correct 227 ms 52332 KB Output is correct
34 Correct 257 ms 54124 KB Output is correct
35 Correct 262 ms 56940 KB Output is correct
36 Correct 244 ms 54380 KB Output is correct