oj.uz

답안 #242187

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242187 2020-06-27T05:17:39 Z oolimry Valley (BOI19_valley) C++14
100 / 100
 957 ms 144924 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<long long,long long> ii;
static vector<ii> adj[100005];
static long long dis[100005];
static long long depth[100005];
static long long vis[100005];
static long long sz[100005];
static long long cented[100005];
static vector<ii> parent[100005];
static vector<long long> nodes;

static vector<ii> disc[100005];
static vector<int> disc2[100005];

static long long low[100005];
static long long high[100005];
int cnt = 0;
long long n, q, S, E;

void dfs(int u){
    sz[u] = 1;
    nodes.push_back(u);
    for(ii v : adj[u]){
        if(sz[v.first] == 0 && !cented[v.first]){
            dis[v.first] = dis[u] + v.second;
            dfs(v.first);
            sz[u] += sz[v.first];

        }
    }
}

void dfs2(int u){
    low[u] = cnt;
    high[u] = cnt;
    cnt++;
    vis[u] = true;
    for(ii v : adj[u]){
        if(!vis[v.first]){
            depth[v.first] = depth[u] + 1;
            dfs2(v.first);
            high[u] = max(high[u],high[v.first]);
        }
    }
}


void recurse(int r, int p){
    nodes.clear();
    dfs(r);
    int centroid;
    for(int u : nodes){
        long long big = sz[r] - sz[u];
        for(ii v : adj[u]){
            if(!cented[v.first] && sz[v.first] < sz[u]){
                big = max(big, sz[v.first]);
            }
        }
        if(2*big <= sz[r]){
            centroid = u;
            break;
        }
    }

    for(int u : nodes){
        sz[u] = 0;
        if(p != -1) parent[u].push_back(ii(p,dis[u]));
        dis[u] = 0;
    }
    cented[centroid] = true;
    for(ii v : adj[centroid]){
        dis[v.first] = v.second;
        if(!cented[v.first]) recurse(v.first, centroid);
    }
}

struct edge{
    long long u;
    long long v;
    long long w;
};

class SegmentTree{
public:
    int nn;
    vector<long long> tree;

    void create(int nnn){
        nn = nnn;
        for(int i = 0;i < 2*nn+4;i++){
            tree.push_back(10234567890123456);
        }
    }

    void update(int i, long long v){
        i += nn;
        while(i > 0){
            tree[i] = min(tree[i], v);
            i >>= 1;
        }
    }

    long long query(int l, int r){
        long long res = 10234567890123456;
        for(l += nn, r += nn;l < r;l >>= 1, r >>= 1){
            if(l&1){
                res = min(res, tree[l]);
                l++;
            }
            if(r&1){
                r--;
                res = min(res,tree[r]);
            }
        }
        return res;
    }
};

static SegmentTree seg[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> S >> q >> E;
    E--;

    edge edges[n-1];
    for(int i = 0;i < n-1;i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back(ii(b,c));
        adj[b].push_back(ii(a,c));
        edges[i] = {a,b,c};
    }

    recurse(0,-1);
    dfs2(0);

    for(int i = 0;i < n;i++){
        parent[i].push_back(ii(i,0));
    }

    for(int i = 0;i < S;i++){
        int x;
        cin >> x;
        x--;
        int preorder = low[x];
        for(ii p : parent[x]){
            disc[p.first].push_back(ii(preorder,p.second));
        }
    }



    for(int i = 0;i < n;i++){
        sort(disc[i].begin(),disc[i].end());
        seg[i].create((int)disc[i].size());
        for(int j = 0;j < disc[i].size();j++){
            ii x = disc[i][j];
            disc2[i].push_back(x.first);
            seg[i].update(j, x.second);
        }
    }

    while(q--){
        int C, R;
        cin >> C >> R;
        C--; R--;

        int subtree;
        int X = edges[C].u;
        int Y = edges[C].v;
        if(depth[X] > depth[Y]){
            subtree = X;
        }
        else{
            subtree = Y;
        }


        int LOW = low[subtree];
        int HIGH = high[subtree];

        bool isRin = (LOW <= low[R] && low[R] <= HIGH);
        bool isEin = (LOW <= low[E] && low[E] <= HIGH);

        if(isRin == isEin){
            cout << "escaped\n";
            continue;
        }

        long long ans = 10234567890123456;
        for(ii P : parent[R]){
            long long res = 10234567890123456;
            int p = P.first;

            bool isPin = (LOW <= low[p] && low[p] <= HIGH);
            if(isPin != isRin){
                continue;
            }
            int lEnd = lower_bound(disc2[p].begin(),disc2[p].end(), LOW) - disc2[p].begin();
            int rEnd = upper_bound(disc2[p].begin(),disc2[p].end(), HIGH) - disc2[p].begin() - 1;
            if(isRin){
                res = min(res, seg[p].query(lEnd,rEnd+1));
            }
            else{
                res = min(res, seg[p].query(0,lEnd));
                res = min(res, seg[p].query(rEnd+1,(int)disc2[p].size()));
            }
            ans = min(ans, res + P.second);
        }



        if(ans > 10234527890123450)
            cout << "oo\n";
        else cout << ans << "\n";
    }

}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:163:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < disc[i].size();j++){
                       ~~^~~~~~~~~~~~~~~~
valley.cpp: In function 'void recurse(int, int)':
valley.cpp:54:9: warning: 'centroid' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int centroid;
         ^~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 13056 KB Output is correct
2 Correct 15 ms 13056 KB Output is correct
3 Correct 14 ms 13056 KB Output is correct
4 Correct 16 ms 13056 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 13056 KB Output is correct
2 Correct 15 ms 13056 KB Output is correct
3 Correct 14 ms 13056 KB Output is correct
4 Correct 16 ms 13056 KB Output is correct
5 Correct 12 ms 13184 KB Output is correct
6 Correct 13 ms 13312 KB Output is correct
7 Correct 14 ms 13312 KB Output is correct
8 Correct 13 ms 13184 KB Output is correct
9 Correct 14 ms 13312 KB Output is correct
10 Correct 14 ms 13312 KB Output is correct
11 Correct 14 ms 13440 KB Output is correct
12 Correct 16 ms 13568 KB Output is correct
13 Correct 15 ms 13696 KB Output is correct
14 Correct 13 ms 13440 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 75552 KB Output is correct
2 Correct 686 ms 102248 KB Output is correct
3 Correct 799 ms 118888 KB Output is correct
4 Correct 957 ms 132324 KB Output is correct
5 Correct 879 ms 132700 KB Output is correct
6 Correct 938 ms 144924 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 13056 KB Output is correct
2 Correct 15 ms 13056 KB Output is correct
3 Correct 14 ms 13056 KB Output is correct
4 Correct 16 ms 13056 KB Output is correct
5 Correct 12 ms 13184 KB Output is correct
6 Correct 13 ms 13312 KB Output is correct
7 Correct 14 ms 13312 KB Output is correct
8 Correct 13 ms 13184 KB Output is correct
9 Correct 14 ms 13312 KB Output is correct
10 Correct 14 ms 13312 KB Output is correct
11 Correct 14 ms 13440 KB Output is correct
12 Correct 16 ms 13568 KB Output is correct
13 Correct 15 ms 13696 KB Output is correct
14 Correct 13 ms 13440 KB Output is correct
15 Correct 460 ms 75552 KB Output is correct
16 Correct 686 ms 102248 KB Output is correct
17 Correct 799 ms 118888 KB Output is correct
18 Correct 957 ms 132324 KB Output is correct
19 Correct 879 ms 132700 KB Output is correct
20 Correct 938 ms 144924 KB Output is correct
21 Correct 279 ms 48340 KB Output is correct
22 Correct 432 ms 58096 KB Output is correct
23 Correct 416 ms 62060 KB Output is correct
24 Correct 487 ms 64744 KB Output is correct
25 Correct 503 ms 71176 KB Output is correct
26 Correct 261 ms 48488 KB Output is correct
27 Correct 408 ms 57600 KB Output is correct
28 Correct 451 ms 62320 KB Output is correct
29 Correct 574 ms 65260 KB Output is correct
30 Correct 588 ms 70252 KB Output is correct
31 Correct 279 ms 51180 KB Output is correct
32 Correct 394 ms 63796 KB Output is correct
33 Correct 489 ms 68592 KB Output is correct
34 Correct 577 ms 72828 KB Output is correct
35 Correct 639 ms 78828 KB Output is correct
36 Correct 560 ms 82800 KB Output is correct