Submission #227926

#	Time	Username	Problem	Language	Result	Execution time	Memory
227926		Hideo	Valley (BOI19_valley)	C++11	100 / 100	369 ms	27284 KiB

valley

//#pragma GCC optimization ("O3")
//#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pl pair < ll, ll >
#define pi pair < int, int >
#define pii pair < ll, pi >
#define next next123
#define left left123

const int N = 1e5 + 7;
const ll INF = 1e15 + 7;

ll d[N], ans[N], t[4 * N], lz[4 * N];
int h[N], tin[N], tout[N], tim;
int n, s, q, rt;

vector < pair < int, ll > > g[N];
vector < pi > ev[N];

struct edge{
    int a, b;
    ll w;
}e[N];

void push (int v, int l, int r){
    if (l != r){
        lz[v + v] += lz[v];
        lz[v + v + 1] += lz[v];
    }
    t[v] += lz[v];
    lz[v] = 0;
}

void upd (int v, int l, int r, int ql, int qr, ll val){
    push(v, l, r);
    if (ql <= l && r <= qr){
        lz[v] = val;
        push(v, l, r);
        return;
    }
    if (r < ql || qr < l)
        return;
    int mid = (l + r) >> 1;
    upd(v + v, l, mid, ql, qr, val);
    upd(v + v + 1, mid + 1, r, ql, qr, val);
    t[v] = min(t[v + v], t[v + v + 1]);
}

ll get (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (ql <= l && r <= qr)
        return t[v];
    if (r < ql || qr < l)
        return INF;
    int mid = (l + r) >> 1;
    return min(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
}

void calc (int v, int p = 0){
    h[v] = h[p] + 1;
    tin[v] = ++tim;
    for (auto to : g[v]){
        if (to.fr != p){
            calc(to.fr, v);
            d[v] = min(d[v], d[to.fr] + to.sc);
        }
    }
    tout[v] = tim;
}

bool check (int v, int u){
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

void dfs (int v, int p = 0){
    upd(1, 1, n, h[v], h[v], d[v]);
    for (auto to : g[v]){
        if (to.fr != p){
            upd(1, 1, n, 1, h[v], to.sc);
            dfs(to.fr, v);
            upd(1, 1, n, 1, h[v], -to.sc);
        }
    }
    for (pi it : ev[v])
        ans[it.sc] = get(1, 1, n, h[it.fr], h[v]);
    upd(1, 1, n, h[v], h[v], -d[v]);
}

main(){
    cin >> n >> s >> q >> rt;
    for (int i = 1; i < n; i++){
        scanf("%d%d%lld", &e[i].a, &e[i].b, &e[i].w);
        g[e[i].a].pb(mk(e[i].b, e[i].w));
        g[e[i].b].pb(mk(e[i].a, e[i].w));
        d[i] = INF;
    }
    d[n] = INF;
    for (int i = 1; i <= s; i++){
        int v;
        scanf("%d", &v);
        d[v] = 0;
    }
    calc(rt);
    for (int i = 1; i <= q; i++){
        int v, b, c;
        scanf("%d%d", &v, &b);
        c = e[v].a;
        if (h[e[v].a] < h[e[v].b])
            c = e[v].b;
        if (check(c, b))
            ev[b].pb(mk(c, i));
        else
            ans[i] = -1;
    }
    dfs(rt);
    for (int i = 1; i <= q; i++){
        if (ans[i] == -1)
            puts("escaped");
        else if (ans[i] >= INF)
            puts("oo");
        else
            printf("%lld\n", ans[i]);
    }
}

Compilation message (stderr)

valley.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
valley.cpp:103:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
valley.cpp: In function 'int main()':
valley.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%lld", &e[i].a, &e[i].b, &e[i].w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &v);
         ~~~~~^~~~~~~~~~
valley.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &b);
         ~~~~~^~~~~~~~~~~~~~~~

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