oj.uz

답안 #161712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161712 2019-11-04T03:00:35 Z karma Valley (BOI19_valley) C++14
100 / 100
 348 ms 53116 KB 
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e5) + 7;
const int logN = 17;
const ll inf = (ll)1e18;
typedef pair<int, int> pii;

ll f[N], res, w, g[N][logN + 1], dis[N][logN + 1];
pii e[N];
bool shop[N];
int n, s, u, v, del, r, q, root, T = 0;
int p[N][logN + 1], in[N], h[N], out[N];
vector<pii> a[N];

void DFS(int u) {
    in[u] = ++T;
    if(shop[u]) f[u] = 0;
    else f[u] = inf;
    for(int j = 1; j <= logN; ++j) {
        p[u][j] = p[p[u][j - 1]][j - 1];
        dis[u][j] = dis[u][j - 1] + dis[p[u][j - 1]][j - 1];
    }
    for(pii& lst: a[u]) {
        int v = lst.fi; ll w = lst.se;
        if(v == p[u][0]) continue;
        p[v][0] = u, dis[v][0] = w;
        h[v] = h[u] + 1;
        DFS(v);
        f[u] = min(f[u], f[v] + w);
    }
    out[u] = ++T;
}

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> s >> q >> root;
    for(int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        e[i] = mp(u, v);
        a[u].pb(v, w), a[v].pb(u, w);
    }
    for(int i = 1; i <= s; ++i) cin >> u, shop[u] = 1;
    DFS(root);
    for(int i = 1; i <= n; ++i) g[i][0] = min(inf, f[p[i][0]] + dis[i][0]);
    for(int j = 1; j <= logN; ++j) {
        for(int i = 1; i <= n; ++i) {
           g[i][j] = min(g[i][j - 1], g[p[i][j - 1]][j - 1] + dis[i][j - 1]);
        }
    }
    while(q --) {
        cin >> del >> r; /// cat canh del va dang o dinh r
        u = e[del].fi, v = e[del].se;
        if(uIsParentOfv(v, u)) swap(u, v); /// u is parent of v
        if(uIsParentOfv(v, r)) {
           res = f[r]; ll d = 0, dep = (h[r] - h[v]);
           for(int i = 0; i <= logN; ++i) {
              if(dep >> i & 1) {
                res = min(res, d + g[r][i]);
                d += dis[r][i];
                r = p[r][i];
              }
           }
           if(res >= inf) cout << "oo\n";
           else cout << res << '\n';
        } else cout << "escaped\n";
    }
}

Compilation message

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

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2936 KB Output is correct
2 Correct 7 ms 2936 KB Output is correct
3 Correct 8 ms 2936 KB Output is correct
4 Correct 7 ms 2936 KB Output is correct

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 49272 KB Output is correct
2 Correct 260 ms 49016 KB Output is correct
3 Correct 265 ms 48832 KB Output is correct
4 Correct 313 ms 50552 KB Output is correct
5 Correct 294 ms 50812 KB Output is correct
6 Correct 291 ms 52488 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2936 KB Output is correct
2 Correct 7 ms 2936 KB Output is correct
3 Correct 8 ms 2936 KB Output is correct
4 Correct 7 ms 2936 KB Output is correct
5 Correct 5 ms 3192 KB Output is correct
6 Correct 6 ms 3192 KB Output is correct
7 Correct 6 ms 3192 KB Output is correct
8 Correct 6 ms 3192 KB Output is correct
9 Correct 6 ms 3192 KB Output is correct
10 Correct 6 ms 3192 KB Output is correct
11 Correct 6 ms 3192 KB Output is correct
12 Correct 6 ms 3192 KB Output is correct
13 Correct 6 ms 3192 KB Output is correct
14 Correct 6 ms 3256 KB Output is correct
15 Correct 244 ms 49272 KB Output is correct
16 Correct 260 ms 49016 KB Output is correct
17 Correct 265 ms 48832 KB Output is correct
18 Correct 313 ms 50552 KB Output is correct
19 Correct 294 ms 50812 KB Output is correct
20 Correct 291 ms 52488 KB Output is correct
21 Correct 208 ms 48564 KB Output is correct
22 Correct 220 ms 48248 KB Output is correct
23 Correct 258 ms 48248 KB Output is correct
24 Correct 287 ms 50168 KB Output is correct
25 Correct 252 ms 52988 KB Output is correct
26 Correct 223 ms 48760 KB Output is correct
27 Correct 260 ms 48376 KB Output is correct
28 Correct 237 ms 48368 KB Output is correct
29 Correct 299 ms 49816 KB Output is correct
30 Correct 327 ms 51280 KB Output is correct
31 Correct 242 ms 48732 KB Output is correct
32 Correct 230 ms 48480 KB Output is correct
33 Correct 282 ms 48504 KB Output is correct
34 Correct 312 ms 50296 KB Output is correct
35 Correct 348 ms 53116 KB Output is correct
36 Correct 285 ms 50356 KB Output is correct