oj.uz

Submission #486511

# Submission time Handle Problem Language Result Execution time Memory
486511 2021-11-11T21:28:29 Z Yazan_Alattar Valley (BOI19_valley) C++14
100 / 100
 298 ms 67496 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

priority_queue < pair <ll,ll> > q;
vector < pair <ll,ll> > adj[M];
int n, s, qry, root, in[M], out[M], timer, v[M], u[M], dep[M];
ll dist[M][20], mn[M][20], anc[M][20], cost[M];
bool shop[M];

void dfs(int node, int p)
{
    cost[node] = (shop[node] ? 0 : 1e18);
    in[node] = ++timer;
    for(auto i : adj[node]){
        if(i.F == p) continue;
        dep[i.F] = dep[node] + 1;
        anc[i.F][0] = node;
        dist[i.F][0] = i.S;
        for(int j = 1; j < 20; ++j){
            anc[i.F][j] = anc[anc[i.F][j - 1]][j - 1];
            dist[i.F][j] = dist[i.F][j - 1] + dist[anc[i.F][j - 1]][j - 1];
        }
        dfs(i.F, node);
        cost[node] = min(cost[node], cost[i.F] + i.S);
    }
    out[node] = ++timer;
    return;
}

void dfs2(int node, int p)
{
    for(auto i : adj[node]){
        if(i.F == p) continue;
        mn[i.F][0] = i.S + cost[node];
        for(int j = 1; j < 20; ++j) if(anc[i.F][j]) mn[i.F][j] = min(mn[i.F][j - 1], mn[anc[i.F][j - 1]][j - 1] + dist[i.F][j - 1]);
        dfs2(i.F, node);
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> s >> qry >> root;
    for(int i = 1; i < n; ++i){
        ll w;
        cin >> v[i] >> u[i] >> w;
        adj[v[i]].pb({u[i], w});
        adj[u[i]].pb({v[i], w});
    }
    for(int i = 1; i <= s; ++i){
        int x;
        cin >> x;
        shop[x] = 1;
    }
    dfs(root, 0);
    dfs2(root, 0);
    int cnt = 1;
    while(qry--){
        int x, node;
        cin >> x >> node;
        int p = v[x];
        if(anc[u[x]][0] == v[x]) p = u[x];
        if(in[node] < in[p] || in[node] > out[p]) cout << "escaped\n";
        else{
            ll ans = cost[node], road = 0;
            for(int j = 19; j >= 0; --j){
                if(dep[anc[node][j]] < dep[p]) continue;
                ans = min(ans, mn[node][j] + road);
                road += dist[node][j];
                node = anc[node][j];
            }
            if(ans == 1e18) cout << "oo\n";
            else cout << ans << endl;
        }
    }
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:80:9: warning: unused variable 'cnt' [-Wunused-variable]
   80 |     int cnt = 1;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2896 KB Output is correct
2 Correct 4 ms 2896 KB Output is correct
3 Correct 3 ms 2896 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2896 KB Output is correct
2 Correct 4 ms 2896 KB Output is correct
3 Correct 3 ms 2896 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 2 ms 3280 KB Output is correct
6 Correct 2 ms 3280 KB Output is correct
7 Correct 2 ms 3280 KB Output is correct
8 Correct 2 ms 3280 KB Output is correct
9 Correct 2 ms 3280 KB Output is correct
10 Correct 3 ms 3324 KB Output is correct
11 Correct 3 ms 3196 KB Output is correct
12 Correct 2 ms 3280 KB Output is correct
13 Correct 3 ms 3340 KB Output is correct
14 Correct 3 ms 3320 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 62096 KB Output is correct
2 Correct 169 ms 61896 KB Output is correct
3 Correct 182 ms 62132 KB Output is correct
4 Correct 219 ms 64400 KB Output is correct
5 Correct 208 ms 64372 KB Output is correct
6 Correct 283 ms 67016 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2896 KB Output is correct
2 Correct 4 ms 2896 KB Output is correct
3 Correct 3 ms 2896 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 2 ms 3280 KB Output is correct
6 Correct 2 ms 3280 KB Output is correct
7 Correct 2 ms 3280 KB Output is correct
8 Correct 2 ms 3280 KB Output is correct
9 Correct 2 ms 3280 KB Output is correct
10 Correct 3 ms 3324 KB Output is correct
11 Correct 3 ms 3196 KB Output is correct
12 Correct 2 ms 3280 KB Output is correct
13 Correct 3 ms 3340 KB Output is correct
14 Correct 3 ms 3320 KB Output is correct
15 Correct 173 ms 62096 KB Output is correct
16 Correct 169 ms 61896 KB Output is correct
17 Correct 182 ms 62132 KB Output is correct
18 Correct 219 ms 64400 KB Output is correct
19 Correct 208 ms 64372 KB Output is correct
20 Correct 283 ms 67016 KB Output is correct
21 Correct 153 ms 61452 KB Output is correct
22 Correct 170 ms 61260 KB Output is correct
23 Correct 186 ms 61512 KB Output is correct
24 Correct 237 ms 64008 KB Output is correct
25 Correct 266 ms 67496 KB Output is correct
26 Correct 153 ms 61528 KB Output is correct
27 Correct 189 ms 61388 KB Output is correct
28 Correct 186 ms 61640 KB Output is correct
29 Correct 230 ms 63272 KB Output is correct
30 Correct 283 ms 65220 KB Output is correct
31 Correct 191 ms 61648 KB Output is correct
32 Correct 229 ms 61492 KB Output is correct
33 Correct 243 ms 61800 KB Output is correct
34 Correct 266 ms 64064 KB Output is correct
35 Correct 298 ms 67492 KB Output is correct
36 Correct 259 ms 63944 KB Output is correct