oj.uz

Submission #983061

# Submission time Handle Problem Language Result Execution time Memory
983061 2024-05-15T07:33:11 Z Br3ad Valley (BOI19_valley) C++14
100 / 100
 294 ms 52368 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 1e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

vector<vector<pair<int, ll>>> adj(N, vector<pair<int, ll>>()), par(20, vector<pair<int, ll>>(N));
vector<pair<int, int>> edge;
vector<int> depth(N), tin(N), sz(N, 1), to(N);
vector<ll> path(N), dp(N);
vector<bool> isShop(N, false);

int entry = 1;
void dfs(int cur, int prev = -1){
    tin[cur] = entry++;
    dp[cur] = (isShop[cur])? path[cur] : INF;
    for(auto [child, weight] : adj[cur]){
        if(child == prev) continue;

        depth[child] = depth[cur] + 1;
        path[child] = path[cur] + weight;
        to[child] = cur;

        dfs(child, cur);

        if(dp[child] != INF) dp[cur] = min(dp[cur], dp[child] + 2*path[child]);
        sz[cur] += sz[child];
    }
    if(dp[cur] != INF) dp[cur] -= 2*path[cur];
}

bool isAncestor(int child, int anc){
    return (tin[anc] <= tin[child] && tin[anc] + sz[anc] > tin[child]);
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // ifstream cin();
    // ofstream cout();
    
    int n, s, q, e;
    cin >> n >> s >> q >> e;
    for(int i = 0; i < n-1; i++){
        int a, b, w;
        cin >> a >> b >> w;
        edge.PB(MP(a, b));
        adj[a].PB(MP(b, w));
        adj[b].PB(MP(a, w));
    }

    for(int i = 0; i < s; i++) {
        int shop;
        cin >> shop;
        isShop[shop] = true;
    }
    
    // let lca(u, v) = w, 
    // dis(u, v) = path[u] - path[w] + path[v] - path[w]
    // let v be the closest shop to w in subtree with root w
    // dp[w] = path[v] - 2*path[w];
    // Transition: dp[w] = min(dp[i] + 2*path[i]) - 2*path[w];

    // Find all dp[i], such that answer for R is path[R] + min(dp[i])

    to[e] = e;
    path[e] = 0;
    dfs(e);

    for(int i = 1; i <= n; i++) par[0][i] = MP(to[i], min(dp[i], dp[to[i]]));
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n; j++){
            par[i][j] = par[i-1][par[i-1][j].f];
            par[i][j].s = min(par[i][j].s, par[i-1][j].s);
        }
    }

    while(q--){
        int block, start;
        cin >> block >> start;

        auto [x, y] = edge[block-1];
        if(depth[x] > depth[y]) swap(x, y);

        if(isAncestor(start, y)){
            int dis = depth[start] - depth[y];
            ll mn = dp[start];

            int cur = start;
            for(int i = 0; i < 20; i++){
                if((dis >> i) & 1){
                    mn = min(mn, par[i][cur].s);
                    cur = par[i][cur].f;
                }
            }
            
            if(mn == INF){
                cout << "oo" << endl;
            }else {
                cout << path[start] + mn << endl;
            }
        }else {
            cout << "escaped" << endl;
        }
    }
}

Compilation message

valley.cpp: In function 'void dfs(int, int)':
valley.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for(auto [child, weight] : adj[cur]){
      |              ^
valley.cpp: In function 'int main()':
valley.cpp:111:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |         auto [x, y] = edge[block-1];
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37340 KB Output is correct
2 Correct 34 ms 37416 KB Output is correct
3 Correct 27 ms 37424 KB Output is correct
4 Correct 27 ms 37184 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37340 KB Output is correct
2 Correct 34 ms 37416 KB Output is correct
3 Correct 27 ms 37424 KB Output is correct
4 Correct 27 ms 37184 KB Output is correct
5 Correct 16 ms 37324 KB Output is correct
6 Correct 16 ms 37184 KB Output is correct
7 Correct 16 ms 37184 KB Output is correct
8 Correct 21 ms 37224 KB Output is correct
9 Correct 18 ms 37320 KB Output is correct
10 Correct 17 ms 37224 KB Output is correct
11 Correct 16 ms 37172 KB Output is correct
12 Correct 16 ms 37180 KB Output is correct
13 Correct 16 ms 37324 KB Output is correct
14 Correct 16 ms 37184 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 43832 KB Output is correct
2 Correct 201 ms 47416 KB Output is correct
3 Correct 221 ms 47656 KB Output is correct
4 Correct 219 ms 49780 KB Output is correct
5 Correct 205 ms 49720 KB Output is correct
6 Correct 229 ms 51768 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37340 KB Output is correct
2 Correct 34 ms 37416 KB Output is correct
3 Correct 27 ms 37424 KB Output is correct
4 Correct 27 ms 37184 KB Output is correct
5 Correct 16 ms 37324 KB Output is correct
6 Correct 16 ms 37184 KB Output is correct
7 Correct 16 ms 37184 KB Output is correct
8 Correct 21 ms 37224 KB Output is correct
9 Correct 18 ms 37320 KB Output is correct
10 Correct 17 ms 37224 KB Output is correct
11 Correct 16 ms 37172 KB Output is correct
12 Correct 16 ms 37180 KB Output is correct
13 Correct 16 ms 37324 KB Output is correct
14 Correct 16 ms 37184 KB Output is correct
15 Correct 294 ms 43832 KB Output is correct
16 Correct 201 ms 47416 KB Output is correct
17 Correct 221 ms 47656 KB Output is correct
18 Correct 219 ms 49780 KB Output is correct
19 Correct 205 ms 49720 KB Output is correct
20 Correct 229 ms 51768 KB Output is correct
21 Correct 188 ms 47084 KB Output is correct
22 Correct 205 ms 47228 KB Output is correct
23 Correct 195 ms 47156 KB Output is correct
24 Correct 212 ms 49208 KB Output is correct
25 Correct 224 ms 52368 KB Output is correct
26 Correct 189 ms 47172 KB Output is correct
27 Correct 189 ms 46896 KB Output is correct
28 Correct 194 ms 47160 KB Output is correct
29 Correct 207 ms 48700 KB Output is correct
30 Correct 259 ms 50484 KB Output is correct
31 Correct 193 ms 47412 KB Output is correct
32 Correct 195 ms 47068 KB Output is correct
33 Correct 234 ms 47512 KB Output is correct
34 Correct 216 ms 49232 KB Output is correct
35 Correct 216 ms 52176 KB Output is correct
36 Correct 200 ms 49040 KB Output is correct