Submission #560096

#	Time	Username	Problem	Language	Result	Execution time	Memory
560096		tamthegod	Valley (BOI19_valley)	C++14	100 / 100	458 ms	67036 KiB

valley

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<cstdio>
#include<bitset>
#include<chrono>
#include<random>
#include<ext/rope>
/* ordered_set
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
#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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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 Log()
{
    for(int i=2; i<maxN; i++)
        lg[i] = lg[i / 2] + 1;
}
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 Solve()
{
    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);
    Log();
    ReadInput();
    Solve();
}

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