Submission #137838

#	Time	Username	Problem	Language	Result	Execution time	Memory
137838		lyc	Valley (BOI19_valley)	C++14	100 / 100	2619 ms	219996 KiB

valley

#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 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41