oj.uz

Submission #137838

# Submission time Handle Problem Language Result Execution time Memory
137838 2019-07-28T10:53:55 Z lyc Valley (BOI19_valley) C++14
100 / 100
 2619 ms 219996 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAX_N = 1e5+5;
const int lgN = 17;

int N, S, Q, E;
vector<ii> al[MAX_N];
struct Edge { int A, B, W; } edge[MAX_N];
bool shop[MAX_N];

// segment tree
struct node {
    int s, e, m; ll v;
    node *l, *r;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), v(1e18) {
        if (s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }

    void update(int x, ll z) {
        if (s == e) { v = z; return; }
        else if (x <= m) l->update(x, z);
        else r->update(x, z);
        v = min(l->v, r->v);
    }

    ll qmin(int x, int y) {
        if (s == x and e == y) return v;
        else if (y <= m) return l->qmin(x, y);
        else if (x >  m) return r->qmin(x, y);
        else return min(l->qmin(x, m), r->qmin(m+1, y));
    }
} *root[lgN];

// dfs and lca
int pre[MAX_N], post[MAX_N], dep[MAX_N], pa[MAX_N][lgN], cnt;
ll dist[MAX_N];
void dfs(int u, int p) {
    pre[u] = ++cnt;
    FOR(k,1,lgN-1) pa[u][k] = pa[u][k-1] == -1 ? -1 : pa[pa[u][k-1]][k-1];
    for (auto v : al[u]) if (v.fi != p) pa[v.fi][0] = u, dist[v.fi] = dist[u]+v.sc, dep[v.fi] = dep[u]+1, dfs(v.fi, u);
    post[u] = cnt;
}
int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a,b);
    RFOR(k,lgN-1,0) if (pa[a][k] != -1 and dep[pa[a][k]] >= dep[b]) a = pa[a][k];
    if (a == b) return a;
    RFOR(k,lgN-1,0) if (pa[a][k] != -1 and pa[b][k] != -1 and pa[a][k] != pa[b][k])
        a = pa[a][k], b = pa[b][k];
    assert(pa[a][0] == pa[b][0]);
    return pa[a][0];
}
inline ll getDist(int a, int b) { return dist[a] + dist[b] - 2*dist[lca(a,b)]; }

// cd
int sub[MAX_N], dad[MAX_N], ptr[lgN];
struct Data { vector<pair<int, ll>> val; int start, depth; } data[MAX_N];
int subtree(int u, int p) {
    sub[u] = 1;
    for (auto v : al[u]) if (v.fi != p and dad[v.fi] == -1) sub[u] += subtree(v.fi, u);
    return sub[u];
}
int centroid(int u, int p, int sz) {
    for (auto v : al[u]) if (v.fi != p and dad[v.fi] == -1 and sub[v.fi] > sz/2) return centroid(v.fi, u, sz);
    return u;
}
void getChildren(int u, int p, ll d, vector<pair<int,ll>>& children) {
    if (shop[u]) children.emplace_back(pre[u],d);
    for (auto v : al[u]) if (v.fi != p and dad[v.fi] == -1) getChildren(v.fi,u,d+v.sc,children);
}
void decomp(int u, int p, int d) {
    int sz = subtree(u, p);
    int c = centroid(u, p, sz);
    dad[c] = p;
    getChildren(c,-1,0,data[c].val);
    sort(ALL(data[c].val));
    data[c].start = ptr[d];
    data[c].depth = d;
    for (auto x : data[c].val) root[d]->update(ptr[d]++, x.sc);
    for (auto v : al[c]) if (dad[v.fi] == -1) decomp(v.fi,c,d+1); 
}
void init_cd() {
    cnt = 0; dist[1] = dep[1] = 0;
    memset(pa, -1, sizeof pa);
    dfs(1,-1);
    FOR(i,1,N) dad[i] = -1;
    FOR(i,0,lgN-1) ptr[i] = 0, root[i] = new node(0,N-1);
    decomp(1,0,0);
}

// solve
ll getAns(int u, int s, int e, bool btw) {
    //cerr << "\t\tgetAns u s e btw " << u << " " << s << " " << e << " " << btw << endl;
    ll ans = 1e18;
    for (int p = u; p != 0; p = dad[p]) {
        ll pdist = getDist(u,p);
        int pdepth = data[p].depth;
        int pstart = data[p].start;
        int pend = data[p].start + SZ(data[p].val) - 1;
        //cerr << "\t\t\t\tp " << p << " pdist " << pdist << " pdepth " << pdepth << " :: ";
        //for (auto x : data[p].val) { cerr << "(" << x.fi << "," << x.sc << ") "; } cerr << endl;

        auto st = pstart + lower_bound(ALL(data[p].val), mp(s,(ll)0)) - data[p].val.begin();
        auto en = pstart + lower_bound(ALL(data[p].val), mp(e,(ll)1e18)) - data[p].val.begin() - 1;
        //cerr << "\t\t\t\t\t\tst " << st << " en " << en << " :: ";
        //FOR(i,0,N-1) { cerr << root[pdepth]->qmin(i,i) << ' '; } 
        //cerr << endl;

        if (btw) {
            if (st > en || st > pend || en < pstart) continue;
            //cerr << "\t\t\t\t\t\tQMIN " << root[pdepth]->qmin(st,en) << endl;
            ans = min(ans, pdist + root[pdepth]->qmin(st,en));
        } else {
            //if (st>pstart) cerr << "\t\t\t\t\t\tQMIN " << root[pdepth]->qmin(pstart,st-1) << endl;
            //if (en<pend) cerr << "\t\t\t\t\t\tQMIN " << root[pdepth]->qmin(en+1,pend) << endl;

            if (st > pstart) ans = min(ans, pdist + root[pdepth]->qmin(pstart,st-1));
            if (en < pend)   ans = min(ans, pdist + root[pdepth]->qmin(en+1,pend));
        }
    }
    return ans;
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> S >> Q >> E;
    FOR(i,1,N-1){
        int A, B, W; cin >> A >> B >> W;
        al[A].emplace_back(B, W);
        al[B].emplace_back(A, W);
        edge[i] = { A, B, W };
    }

    FOR(i,1,S){
        int C; cin >> C;
        shop[C] = 1;
    }
    init_cd();

    FOR(i,1,Q){
        int I, R; cin >> I >> R;
        int down = pre[edge[I].A] > pre[edge[I].B] ? edge[I].A : edge[I].B;
        //cerr << "\t\tEDGE " << edge[i].A << " " << edge[i].B << " :: " << edge[i].W << endl;
        //cerr << "\t\tDOWN " << down << endl;
        bool a = (pre[down] <= pre[R] and pre[R] <= post[down]);
        bool b = (pre[down] <= pre[E] and pre[E] <= post[down]);
        if (a ^ b) {
            ll ans = getAns(R, pre[down], post[down], a);
            if (ans == 1e18) cout << "oo" << '\n';
            else cout << ans << '\n';
        } else {
            cout << "escaped" << '\n';
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12792 KB Output is correct
2 Correct 17 ms 12792 KB Output is correct
3 Correct 17 ms 12792 KB Output is correct
4 Correct 18 ms 12792 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12792 KB Output is correct
2 Correct 17 ms 12792 KB Output is correct
3 Correct 17 ms 12792 KB Output is correct
4 Correct 18 ms 12792 KB Output is correct
5 Correct 16 ms 14204 KB Output is correct
6 Correct 17 ms 14292 KB Output is correct
7 Correct 17 ms 14200 KB Output is correct
8 Correct 16 ms 14172 KB Output is correct
9 Correct 17 ms 14200 KB Output is correct
10 Correct 17 ms 14200 KB Output is correct
11 Correct 18 ms 14328 KB Output is correct
12 Correct 18 ms 14328 KB Output is correct
13 Correct 18 ms 14456 KB Output is correct
14 Correct 17 ms 14328 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 195584 KB Output is correct
2 Correct 1438 ms 202980 KB Output is correct
3 Correct 1871 ms 208612 KB Output is correct
4 Correct 2619 ms 215240 KB Output is correct
5 Correct 1101 ms 215480 KB Output is correct
6 Correct 1740 ms 219996 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12792 KB Output is correct
2 Correct 17 ms 12792 KB Output is correct
3 Correct 17 ms 12792 KB Output is correct
4 Correct 18 ms 12792 KB Output is correct
5 Correct 16 ms 14204 KB Output is correct
6 Correct 17 ms 14292 KB Output is correct
7 Correct 17 ms 14200 KB Output is correct
8 Correct 16 ms 14172 KB Output is correct
9 Correct 17 ms 14200 KB Output is correct
10 Correct 17 ms 14200 KB Output is correct
11 Correct 18 ms 14328 KB Output is correct
12 Correct 18 ms 14328 KB Output is correct
13 Correct 18 ms 14456 KB Output is correct
14 Correct 17 ms 14328 KB Output is correct
15 Correct 910 ms 195584 KB Output is correct
16 Correct 1438 ms 202980 KB Output is correct
17 Correct 1871 ms 208612 KB Output is correct
18 Correct 2619 ms 215240 KB Output is correct
19 Correct 1101 ms 215480 KB Output is correct
20 Correct 1740 ms 219996 KB Output is correct
21 Correct 426 ms 184092 KB Output is correct
22 Correct 567 ms 183676 KB Output is correct
23 Correct 672 ms 183672 KB Output is correct
24 Correct 898 ms 185572 KB Output is correct
25 Correct 790 ms 187812 KB Output is correct
26 Correct 431 ms 184072 KB Output is correct
27 Correct 520 ms 183792 KB Output is correct
28 Correct 726 ms 183824 KB Output is correct
29 Correct 927 ms 185960 KB Output is correct
30 Correct 931 ms 188000 KB Output is correct
31 Correct 503 ms 185440 KB Output is correct
32 Correct 715 ms 186104 KB Output is correct
33 Correct 938 ms 186616 KB Output is correct
34 Correct 1428 ms 189220 KB Output is correct
35 Correct 917 ms 191456 KB Output is correct
36 Correct 671 ms 194400 KB Output is correct