Submission #696155

#TimeUsernameProblemLanguageResultExecution timeMemory
696155vjudge1Valley (BOI19_valley)C++17
100 / 100
424 ms67084 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const int maxN = 1e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, s, Q, e;
vector<int> adj[maxN];
bool is_shop[maxN];
map<pair<int, int>, int> id, dist;
int depth[maxN], lg[maxN];
int f[maxN][21];
int w[maxN];
pair<int, int> edge[maxN];
int d[maxN], dmin[maxN];
int dp[maxN][21];
int timein[maxN], timeout[maxN];
struct TQuery
{
    int r, id;
};
int res[maxN];
int Time = 0;

void predfs(int u, int par)
{
    timein[u] = ++Time;
    dmin[u] = (is_shop[u]) ? d[u] : oo;
    for(int v : adj[u])
    {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        f[v][0] = u;
        d[v] = d[u] + dist[{u, v}];
        for(int i=1; i<=lg[n]; i++)
            f[v][i] = f[f[v][i - 1]][i - 1];
        predfs(v, u);
        dmin[u] = min(dmin[u], dmin[v]);
    }
    timeout[u] = Time;
}
void rmq(int u, int par)
{
    dp[u][0] = dmin[u] - 2 * d[u];
    for(int i=1; i<=19; i++)
        dp[u][i] = min(dp[u][i - 1], dp[f[u][i - 1]][i - 1]);
    for(int v : adj[u])
    {
        if(v == par) continue;
        rmq(v, u);
    }
}
bool chk(int u, int v)
{
    return timein[u] <= timein[v] && timeout[v] <= timeout[u];
}
int get(int u, int v)
{
    int res = dp[v][0];
    for(int i=20; i>=0; i--)
    {
        if(f[u][i] && chk(v, f[u][i]))
        {
            res = min(res, dp[u][i]);
            u = f[u][i];
        }
    }
    return res;
}
void ReadInput()
{
    cin >> n >> s >> Q >> e;
    for(int i=1; i<n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = {u, v};
        adj[u].pb(v);
        adj[v].pb(u);
        dist[{u, v}] = dist[{v, u}] = w;
    }
    for(int i=1; i<=s; i++)
    {
        int x;
        cin >> x;
        is_shop[x] = 1;
    }
}

void sol()
{
    for(int i=2; i<maxN; i++)
        lg[i] = lg[i / 2] + 1;
    cin >> n >> s >> Q >> e;
    for(int i=1; i<n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = {u, v};
        adj[u].pb(v);
        adj[v].pb(u);
        dist[{u, v}] = dist[{v, u}] = w;
    }
    for(int i=1; i<=s; i++)
    {
        int x;
        cin >> x;
        is_shop[x] = 1;
    }
    predfs(e, 0);
    rmq(e, 0);
    for(int i=1; i<=Q; i++)
    {
        int id, r;
        cin >> id >> r;
        int u = edge[id].fi, v = edge[id].se;
        int w = chk(u, v) ? v : u;//cout << ;return;
        if(!chk(w, r)) cout << "escaped\n";
        else
        {
            int res = get(r, w) + d[r];
            if(res >= (int)1e15) cout << "oo\n";
            else cout << res << '\n';
        }
    }

}
int32_t main()
{
   // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    sol();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...