Submission #674649

#	Time	Username	Problem	Language	Result	Execution time	Memory
674649		AmirH	Valley (BOI19_valley)	C++14	100 / 100	193 ms	68288 KiB

valley

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<bitset>
#include<queue>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<unordered_map>
#include<list>
#include<utility>
#include<stack>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
#define cl clear
#define F  first
#define S  second
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
const int MAX_N = 2e5 + 25;
const ll INF = 1e18;
const int inf = 1e9;
const int lgg = 20;
int n, s, q, e;
vector<pii> adj[MAX_N];
bool mark[MAX_N];
int par[MAX_N];
ll magic[MAX_N];
ll dist[MAX_N];
int height[MAX_N];
ll lift[MAX_N][lgg + 10];
ll lift_min[MAX_N][lgg + 10];
vector<pii> edge;
int baz[MAX_N];
int bas[MAX_N];
int d = 0;
void free() {
    #ifndef ONLINE_JUDGE
        freopen("inputi.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
}
void build_lift() {
    for(int i = 1; i <= n; i++) {
        lift[i][0] = i;
        lift_min[i][0] = magic[i];
    }
    for(int i = 1; i <= lgg; i++) {
        for(int j = 1; j <= n; j++) {
            if((1 << (i - 1)) <= height[j]) {
                if(i == 1) {
                    lift[j][i] = par[j];
                    lift_min[j][i] = min(magic[j], magic[par[j]]);
                }
                else {
                    lift[j][i] = lift[lift[j][i - 1]][i - 1];
                    lift_min[j][i] = min(lift_min[lift[j][i - 1]][i - 1], lift_min[j][i - 1]);
                }
            }
        }
    }
}

ll get_min(int v, int h) {
    if(!h)
        return magic[v];
    int chap = 31 - __builtin_clz(h);
    return min(lift_min[v][chap + 1], get_min(lift[v][chap + 1], h - (1 << chap)));
}

void sfd(int v, int s) {
    if(mark[v])
        magic[v] = dist[v];
    else
        magic[v] = INF;
    for(auto i : adj[v]) {
        if(i.first != s) {
            sfd(i.first, v);
            magic[v] = min(magic[v], magic[i.first]);
        }
    }
}

void dfs(int v, int s) {
    d++;
    baz[v] = d;
    for(auto i : adj[v]) {
        if(i.first != s) {
            par[i.first] = v;
            dist[i.first] = dist[v] + i.second;
            height[i.first] = height[v] + 1;
            dfs(i.first, v);
        }
    }
    d++;
    bas[v] = d;
}

void input() {
    cin >> n >> s >> q >> e;
    for(int i = 1; i < n; i++) {
        int x, y, z; cin >> x >> y >> z;
        adj[x].pb({y, z});
        adj[y].pb({x, z});
        edge.pb({x, y});
    }
    for(int i = 1; i <= s; i++) {
        int x; cin >> x;
        mark[x] = true;
    }
}

void solve() {
    par[e] = 0;
    dist[e] = 0;
    height[e] = 0;
    dfs(e, 0);
    sfd(e, 0);
    for(int i = 1; i <= n; i++)
        magic[i] -= (2 * dist[i]);
    build_lift();
}

void output() {
    while(q--) {
        int l, y; cin >> l >> y;
        l--;
        int x;
        if(height[edge[l].first] > height[edge[l].second])
            x = edge[l].first;
        else
            x = edge[l].second;
        if(baz[x] <= baz[y] && bas[x] >= bas[y]) {
            ll res = get_min(y, height[y] - height[x]) + dist[y];
            if(res > 1e15)
                cout << "oo" << '\n';
            else
            cout << res << '\n';
        }
        else {
            cout << "escaped" << '\n';
        }
    }
}
int main() {
    faster; //free();
    input();
    solve();
    output();
}

Compilation message (stderr)

valley.cpp: In function 'void free()':
valley.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen("inputi.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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