Submission #1104650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104650		tuannm	Valley (BOI19_valley)	C++17	100 / 100	120 ms	35144 KiB

valley

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const long long inf = 1e16;
const string NAME = "landslide";
int n, s, q, h;
int pos[N];
vector<ii> adj[N];

struct edge{
    int u, v, w;

    edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
};

edge ed[N];

long long nearest[N], dist[N], jump[20][N];
int d[N], lg[N], in[N], out[N], cnt;
int p[20][N];

void DFS(int u){
    in[u] = ++cnt;

    for(auto [v, w] : adj[u]){
        if(v == p[0][u])
            continue;

        p[0][v] = u;
        d[v] = d[u] + 1;
        dist[v] = dist[u] + w;
        for(int i = 1; i <= lg[d[v]]; ++i)
            p[i][v] = p[i - 1][p[i - 1][v]];

        DFS(v);
    }

    out[u] = cnt;
}

void DFS_nearest(int u){
    for(auto [v, w] : adj[u]){
        if(v == p[0][u])
            continue;

        DFS_nearest(v);
        nearest[u] = min(nearest[u], nearest[v]);
    }
}

bool isAncestor(int u, int v){
    return in[u] <= in[v] && in[v] <= out[u];
}

long long minPath(int u, int v){
    long long res = inf;
    int k = d[v] - d[u];

    for(int i = lg[k]; i >= 0; --i)
        if((k >> i) & 1)
            res = min(res, jump[i][v]), v = p[i][v];

    return min(res, nearest[u]);
}

void inp(){
    cin >> n >> s >> q >> h;

    for(int i = 1; i < n; ++i){
        int u, v, w;
        cin >> u >> v >> w;

        ed[i] = edge(u, v, w);
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }

    for(int i = 1; i <= s; ++i)
        cin >> pos[i];
}

void init(){
    for(int i = 2; i <= n; ++i)
        lg[i] = lg[i / 2] + 1;

    for(int i = 1; i <= n; ++i)
        nearest[i] = inf;

    DFS(h);

    for(int i = 1; i <= s; ++i)
        nearest[pos[i]] = dist[pos[i]];

    DFS_nearest(h);

    for(int i = 1; i <= n; ++i){
        if(nearest[i] < inf)
            nearest[i] -= 2LL * dist[i];

        jump[0][i] = nearest[i];
    }

    for(int l = 1; l <= lg[n]; ++l)
        for(int i = 1; i <= n; ++i)
            jump[l][i] = min(jump[l - 1][i], jump[l - 1][p[l - 1][i]]);

    for(int i = 1; i < n; ++i){
        auto [u, v, w] = ed[i];

        if(in[u] > in[v])
            swap(u, v);

        ed[i] = edge(u, v, w);
    }
}

void solve(){
    init();

    while(q--){
        int id, u;
        cin >> id >> u;

        int v = ed[id].v;

        if(!isAncestor(v, u))
            cout << "escaped\n";
        else{
            long long res = minPath(v, u) + dist[u];

            if(res >= inf)
                cout << "oo\n";
            else
                cout << res << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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