Submission #931065

#	Time	Username	Problem	Language	Result	Execution time	Memory
931065		efedmrlr	Valley (BOI19_valley)	C++17	100 / 100	177 ms	92980 KiB

valley

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e17;
const int N = 2e5+5;
const int ALPH = 26;
const int LGN = 20;
constexpr int MOD = 1e9+7;
const int MX = 1e16;
int n,m,q,s,e;
vector<vector<array<int,3> > > adj(N, vector<array<int,3> >());
vector<vector<int> > anc(LGN, vector<int>(N, 0)), mns(LGN, vector<int>(N, INF));
vector<int> tin(N, 0), dp(N, INF);
vector<bool> spec(N, 0);
vector<int> find_edge(N, 0), dep(N, 0);
vector<int> subt(N, 0), cost(N, 0);
int timer = 1;
void dfs(int node, int par) {
    tin[node] = timer++;
    anc[0][node] = par;
    if(spec[node]) dp[node] = 0;
    subt[node] = 1;
    for(auto itr = adj[node].begin(); itr != adj[node].end();) {
        auto &c = *itr;
        if(c[0] == par) {
            itr = adj[node].erase(itr);
            continue;
        }
        find_edge[c[2]] = c[0];
        dep[c[0]] = dep[node] + 1ll;
        cost[c[0]] = cost[node] + c[1];
        dfs(c[0], node);
        subt[node] += subt[c[0]];
        dp[node] = min(dp[node], dp[c[0]] + c[1]);
        itr++;
    }
}
void prec() {
    for(int i = 1; i<=n; i++) mns[0][i] = dp[i];
    for(int k = 1; k < LGN; k++) {
        for(int i = 1; i <= n; i++) {
            anc[k][i] = anc[k - 1][anc[k - 1][i]];
            mns[k][i] = min(mns[k - 1][i], mns[k - 1][anc[k - 1][i]]);
        }
    }
}

int mindp(int x, int y) {
    int ret = INF;
    for(int k = LGN - 1; k >= 0; k--) {
        if(dep[anc[k][x]] >= dep[y]) {
            ret = min(ret, mns[k][x]);
            x = anc[k][x];
        }
    }   
    ret = min(ret, mns[0][x]);
    return ret;
}

inline void solve() {
    cin>>n>>s>>q>>e;
    REP(i, n - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w, i + 1});
        adj[v].pb({u, w, i + 1});
    }
    REP(i, s) {
        int tmp;
        cin >> tmp;
        spec[tmp] = 1;
    }
    dfs(e, 0);
    for(int i = 1; i<=n; i++) {
        dp[i] -= cost[i];
    }
    prec();
    REP(z, q) {
        int I,R;
        cin >> I >> R;
        int sub = find_edge[I];

        if(tin[sub] <= tin[R] && tin[R] <= tin[sub] + subt[sub] - 1ll) {
            int ans = mindp(R, sub);
            if(ans >= MX) {
                cout << "oo\n";
            }
            else {
                cout << ans + cost[R] << "\n";
            }
        }
        else {
            cout << "escaped\n";
        }
    }
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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