oj.uz

답안 #227926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
227926 2020-04-29T09:13:37 Z Hideo Valley (BOI19_valley) C++11
100 / 100
 369 ms 27284 KB 
//#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5376 KB Output is correct
2 Correct 11 ms 5248 KB Output is correct
3 Correct 11 ms 5376 KB Output is correct
4 Correct 11 ms 5376 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5376 KB Output is correct
2 Correct 11 ms 5248 KB Output is correct
3 Correct 11 ms 5376 KB Output is correct
4 Correct 11 ms 5376 KB Output is correct
5 Correct 10 ms 5248 KB Output is correct
6 Correct 10 ms 5120 KB Output is correct
7 Correct 10 ms 5248 KB Output is correct
8 Correct 10 ms 5248 KB Output is correct
9 Correct 11 ms 5248 KB Output is correct
10 Correct 9 ms 5248 KB Output is correct
11 Correct 10 ms 5248 KB Output is correct
12 Correct 12 ms 5248 KB Output is correct
13 Correct 10 ms 5248 KB Output is correct
14 Correct 9 ms 5248 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 286 ms 20456 KB Output is correct
2 Correct 307 ms 20088 KB Output is correct
3 Correct 333 ms 19920 KB Output is correct
4 Correct 369 ms 23416 KB Output is correct
5 Correct 308 ms 22516 KB Output is correct
6 Correct 341 ms 26872 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5376 KB Output is correct
2 Correct 11 ms 5248 KB Output is correct
3 Correct 11 ms 5376 KB Output is correct
4 Correct 11 ms 5376 KB Output is correct
5 Correct 10 ms 5248 KB Output is correct
6 Correct 10 ms 5120 KB Output is correct
7 Correct 10 ms 5248 KB Output is correct
8 Correct 10 ms 5248 KB Output is correct
9 Correct 11 ms 5248 KB Output is correct
10 Correct 9 ms 5248 KB Output is correct
11 Correct 10 ms 5248 KB Output is correct
12 Correct 12 ms 5248 KB Output is correct
13 Correct 10 ms 5248 KB Output is correct
14 Correct 9 ms 5248 KB Output is correct
15 Correct 286 ms 20456 KB Output is correct
16 Correct 307 ms 20088 KB Output is correct
17 Correct 333 ms 19920 KB Output is correct
18 Correct 369 ms 23416 KB Output is correct
19 Correct 308 ms 22516 KB Output is correct
20 Correct 341 ms 26872 KB Output is correct
21 Correct 289 ms 19936 KB Output is correct
22 Correct 289 ms 19552 KB Output is correct
23 Correct 296 ms 19576 KB Output is correct
24 Correct 314 ms 23320 KB Output is correct
25 Correct 299 ms 27284 KB Output is correct
26 Correct 310 ms 19928 KB Output is correct
27 Correct 275 ms 19580 KB Output is correct
28 Correct 302 ms 19576 KB Output is correct
29 Correct 331 ms 22008 KB Output is correct
30 Correct 349 ms 24016 KB Output is correct
31 Correct 272 ms 19960 KB Output is correct
32 Correct 295 ms 19612 KB Output is correct
33 Correct 295 ms 19840 KB Output is correct
34 Correct 311 ms 22904 KB Output is correct
35 Correct 334 ms 27256 KB Output is correct
36 Correct 288 ms 22520 KB Output is correct