Submission #725800

#	Time	Username	Problem	Language	Result	Execution time	Memory
725800		PenguinsAreCute	Valley (BOI19_valley)	C++17	36 / 100	588 ms	262144 KiB

valley

// "Always use complex numbers rather than pears." - A Rafflesian Y1
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re real()
#define im imag()
#define mp make_pair
#define pb push_back
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMn(a,b) a = min(a,b)
typedef complex<int> ii;
typedef vector<ii> vii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define MAXN 201210
#define MAXH 19
#define INF 31415926535897932
vii adj[MAXN];
int ctrP[MAXN], sbtree[MAXN], ctrH[MAXN];
int h[MAXN], rtdst[MAXN], pre[MAXN], post[MAXN],sparsetable[2*MAXN][MAXH], fEuler[MAXN], logarithm[2*MAXN], cnt, cnt2;
struct node{
    int s, e, v, mid;
    node *l, *r;
    node(int _s, int _e) {
        s=_s;e=_e;mid=(s+e)>>1;v=INF;
        l = r = nullptr;
    }
    void create() {
        if(s!=e&&!l) {
            l=new node(s,mid);
            r=new node(mid+1,e);
        }
    }
    void update(int x, int u){
        if(s==e) {stMn(v,u);return;}
        create();
        if(x<=mid)l->update(x,u);
        else r->update(x,u);
        v=min(l->v,r->v);
    }
    int query(int x,int y) {
        if(s==x&&e==y)return v;
        if(y<=mid)return (l==nullptr)?INF:l->query(x,y);
        else if(x>mid)return (r==nullptr)?INF:r->query(x,y);
        else return min((l==nullptr)?INF:l->query(x,mid),(r==nullptr)?INF:r->query(mid+1,y));
    }
};
void dfs_reg(int x, int par) {
    pre[x]=cnt++;
    sparsetable[cnt2][0] = h[x];
    fEuler[x] = cnt2++;
    for(auto i: adj[x]) if(i.re != par) {
        h[i.re] = h[x] + i.im;
        rtdst[i.re] = rtdst[x] + 1;
        dfs_reg(i.re, x);
        sparsetable[cnt2++][0]=h[x];
    }
    post[x]=cnt-1;
}
void fnd() {
    logarithm[1] = 0;
    REP(i, 2, 2 * MAXN) logarithm[i] = logarithm[i/2] + 1;
}
void constructST() {
    REP(i, 1, MAXH) REP(j, 0, 2 * MAXN) {
        if(j <= 2 * MAXN - (1<<i)) {
            sparsetable[j][i] = min(sparsetable[j][i-1], sparsetable[j+(1<<(i-1))][i-1]);
        }
    }
}
int lca(int a, int b) {
    if(fEuler[a] > fEuler[b]) swap(a, b);
    int df = fEuler[b] - fEuler[a] + 1;
    int h = logarithm[df];
    return min(sparsetable[fEuler[a]][h],sparsetable[fEuler[b]+1-(1<<h)][h]);
}
int dfs_sb3(int x, int par) {
    sbtree[x] = 1;
    for(auto i: adj[x]) if(i.re != par && ctrH[i.re] == -1) {
        sbtree[x] += dfs_sb3(i.re, x);
    }
    return sbtree[x];
}
int dfs_ctr(int u, int p, int n) {
	for (auto v : adj[u]) if(ctrH[v.re] == -1) {
		if (v.re != p && sbtree[v.re] > n / 2) {
			return dfs_ctr(v.re, u, n);
		}
	}
	return u;
}
void ctr3(int u, int p, int l) {
	int n = dfs_sb3(u, p);
	int cent = dfs_ctr(u, p, n);
	ctrP[cent] = p;
	ctrH[cent] = l;
	for (auto v : adj[cent]) {
		if (ctrH[v.re] != -1) continue;
		ctr3(v.re, cent, l + 1);
	}
}
int32_t main() {
	//speed;
    int n, s, q, e, w, I; cin >> n>>s>>q>>e;
    int a[n],b[n];
    REP(i, 1, n) {
        cin >> a[i] >> b[i] >> w;
        adj[a[i]].pb(ii(b[i],w));
        adj[b[i]].pb(ii(a[i],w));
    }
    REP(i, 0, MAXN) ctrH[i] = -1;
    node *segtree[n+5];
    REP(i, 1, n+1) segtree[i] = new node(0, n-1);
    dfs_reg(e, -1); ctr3(e, -1, 0);
    fnd(); constructST();
    REP(i,0,s) {
        cin>>w;
        int cur = w;
        while(cur != -1) {
            segtree[cur]->update(pre[w], h[cur]+h[w]-2*lca(cur,w));
            cur = ctrP[cur];
        }
    }
    while(q--) {
        cin >> I >> w;
        if(h[a[I]]>h[b[I]]) swap(a[I],b[I]);
        if(pre[b[I]]>pre[w] || post[b[I]]<pre[w]) cout << "escaped\n";
        else {
            int cur = w; int ans = INF;
            while(cur != -1) {
                stMn(ans,segtree[cur]->query(pre[b[I]],post[b[I]])+h[cur]+h[w]-2*lca(cur,w));
                cur = ctrP[cur];
            }
            if(ans<INF)cout << ans << "\n";
            else cout << "oo\n";
        }
    }
}

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