Submission #560016

#	Time	Username	Problem	Language	Result	Execution time	Memory
560016		Notred132	Valley (BOI19_valley)	C++17	100 / 100	221 ms	36780 KiB

valley

#include <iostream>
#include <vector>

#define fi first
#define se second

using namespace std;
const long long maxw = 1e18;
const int maxn = 1e5 + 5;
int n, s, q, e;
int in[maxn], out[maxn];
vector <pair <int, int>> adj[maxn];
int cnt;
long long d[maxn];
int deg[maxn];
long long f[maxn][18], g[maxn];
bool dd[maxn];
int p1[maxn][18];

struct TEdge {
    int u, v, w;
};

 TEdge edg[maxn];

 void DFS(int u, int p) {
    in[u] = ++cnt;
    if(dd[u]) g[u] = 0;
    for(pair <int, int> i : adj[u]) {
        if(i.fi == p) continue;
        int v = i.fi;
        int w = i.se;
        d[v] = d[u] + w;
        deg[v] = deg[u] + 1;
        p1[v][0] = u;
        for(int j = 1; (1 << j) <= deg[v]; ++j) p1[v][j] = p1[p1[v][j - 1]][j - 1];
        DFS(i.fi, u);
        g[u] = min(g[u], g[v] + w);
    }
//    f[u][0] = g[u] - d[u];
//    for(int j = 1; (1 << j) <= deg[u] + 1; ++j) f[u][j] = min(f[u][j - 1], f[p1[u][j - 1]][j - 1]);
    out[u] = ++cnt;
 }

 void DFS1(int u, int p) {
    for(auto i : adj[u]) {
        if(i.fi == p) continue;
        int v = i.fi;
        int w = i.se;
        if(g[v] == 1e18) f[v][0] = 1e18;
        else f[v][0] = g[v] - d[v];
        for(int j = 1; (1 << j) <= deg[v] + 1; ++j) f[v][j] = min(f[v][j - 1], f[p1[v][j - 1]][j - 1]);
        DFS1(v, u);
    }
 }

long long solve(int u, int v) {
    int tmp = deg[v] - deg[u] + 1;
    long long res = 1e18;
    int tmp1 = 0;
    while(tmp) {
        if(tmp % 2) {
            res = min(res, f[v][tmp1]);
            v = p1[v][tmp1];
        }
        ++tmp1;
        tmp /= 2;
    }
    return res;
}



int main()
{
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
    cin >> n >> s >> q >> e;
    for(int i = 1; i < n; ++i) {
        cin >> edg[i].u >> edg[i].v >> edg[i].w;
        adj[edg[i].u].push_back({edg[i].v, edg[i].w});
        adj[edg[i].v].push_back({edg[i].u, edg[i].w});
    }
    for(int i = 1; i <= s; ++i) {
        int u;
        cin >> u;
        dd[u] = 1;
    }
    fill(g + 1, g + n + 1, 1e18);
    DFS(e, 0);
    DFS1(e, 0);
    while(q--) {
        int id, c;
        cin >> id >> c;
        int u = edg[id].u;
        int v = edg[id].v;
        if(p1[v][0] == u) swap(u, v);
        if(in[u] > in[c] || out[u] < out[c]) {
            cout << "escaped" << '\n';
            continue;
        }
        long long ans = solve(u, c);
        if(ans == 1e18) cout << "oo" << '\n';
        else cout << ans + d[c] << '\n';
    }
    return 0;
}

Compilation message (stderr)

valley.cpp: In function 'void DFS1(int, int)':
valley.cpp:49:13: warning: unused variable 'w' [-Wunused-variable]
   49 |         int w = i.se;
      |             ^

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