oj.uz

Submission #697916

# Submission time Handle Problem Language Result Execution time Memory
697916 2023-02-11T10:34:46 Z bLIC Valley (BOI19_valley) C++17
100 / 100
 230 ms 52132 KB 
/**
 *  Author: Anil Byar
**/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;

// template<class T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;



#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x).size()
#define ft first
#define sd second
#define pb push_back

// Source: https://codeforces.com/blog/entry/68809
// { start
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// } end


typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef vector<vl> vvl;

#define dbg if(0)

const ll MOD = 1e9+7;
const ll INFLL = 1e18+5;
const int INF = 1e9;
const int maxN = 1e5+5;
const int maxK = 18;

void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;}

template<class T>
istream& operator>>(istream&in, vector<T>&v){
    for (T& x:v) in>>x;
    return in;
}
template<class T>
ostream& operator<<(ostream&out, vector<T>&v){
    for (T& x:v) out<<x<<' ';
    cout<<'\n';
    return out;
}

vii adj[maxN];
int dep[maxN];
int par[maxN][maxK];
ll dist[maxN][maxK];
bool shop[maxN];
ll mnshop[maxN];
ll mnshopup[maxN][maxK];

void dfs(int node, int p = -1){
    if (shop[node]) mnshop[node] = 0;

    for (auto x:adj[node]){
        int v = x.ft, w = x.sd;
        if (v==p) continue;
        par[v][0] = node;
        dist[v][0] = w;
        dep[v] = dep[node] + 1;
        dfs(v, node);
        mnshop[node] = min(mnshop[node], mnshop[v]+w);
    }
}

int kup(int x, int k){
    for (int i = 0;i<maxK;i++){
        if ((k>>i)&1) x = par[x][i];
    }
    return x;
}

ll getbest(int from, int up){
    ll d = 0;
    ll ans = mnshop[from];
    for (int i = 0;i<maxK;i++){
        if (up>>i&1){
            ans = min(ans, d+mnshopup[from][i]);
            d += dist[from][i];
            from = par[from][i];
        }
    }
    return ans;
}

void solve(){
    // ll x = 0;
    // memset(&x, 127, sizeof(x));
    // cout<<x;
    int n, s, q, e;
    cin>>n>>s>>q>>e;
    vii edges(n);
    for (int i = 1;i<n;i++){
        int u, v, w;cin>>u>>v>>w;
        edges[i] = {u, v};
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for (int i = 0;i<s;i++){
        int x;cin>>x;
        shop[x] = 1;
    }
    for (int i = 0;i<=n;i++){
        for (int j = 0;j<maxK;j++) {
            dist[i][j] = INFLL;
            mnshopup[i][j] = INFLL;
            mnshop[i] = INFLL;
        }
    }
    // memset(dist, 127, sizeof(dist));
    // memset(mnshop, 127, sizeof(mnshop));
    // memset(mnshopup, 127, sizeof(mnshopup));
    dfs(e);
    for (int i = 1;i<=n;i++){
        mnshopup[i][0] = min(mnshop[i], mnshop[par[i][0]] + dist[i][0]);
    }
    for (int i = 1;i<maxK;i++){
        for (int j = 1;j<=n;j++){
            par[j][i] = par[par[j][i-1]][i-1];
            dist[j][i] = dist[par[j][i-1]][i-1] + dist[j][i-1];
            mnshopup[j][i] = min(mnshopup[j][i-1], mnshopup[par[j][i-1]][i-1] + dist[j][i-1]);
        }
    }

    while(q--){
        int i, r;cin>>i>>r;
        int v = (dep[edges[i].ft]<dep[edges[i].sd]?edges[i].sd:edges[i].ft);
        if (dep[v]>dep[r] || kup(r, dep[r]-dep[v])!=v) { // is v ancestor of r// can also be checked by st < st and en > en
            cout<<"escaped\n";
        }else {
            int up = dep[r]-dep[v];
            ll ans = getbest(r, up);
            if (ans!=INFLL) cout<<ans<<'\n';
            else cout<<"oo\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

// #define _DEBUG
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.out", "w", stdout);
    int tt = clock();
#endif

    int t=1, i = 1;
    // cin>>t;
    while(t--){
        // cout<<"Case #"<<i++<<": ";
        solve();
        cout<<'\n';
    }
#ifdef _DEBUG
    cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl;
    tt = clock();
#endif
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:195:14: warning: unused variable 'i' [-Wunused-variable]
  195 |     int t=1, i = 1;
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 5 ms 2812 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 5 ms 2812 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 2 ms 3072 KB Output is correct
10 Correct 2 ms 3116 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 3 ms 3072 KB Output is correct
13 Correct 3 ms 3156 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 48332 KB Output is correct
2 Correct 162 ms 47908 KB Output is correct
3 Correct 184 ms 47964 KB Output is correct
4 Correct 201 ms 49744 KB Output is correct
5 Correct 169 ms 49744 KB Output is correct
6 Correct 230 ms 51780 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 4 ms 2900 KB Output is correct
3 Correct 5 ms 2812 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 2 ms 3072 KB Output is correct
10 Correct 2 ms 3116 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 3 ms 3072 KB Output is correct
13 Correct 3 ms 3156 KB Output is correct
14 Correct 3 ms 3156 KB Output is correct
15 Correct 148 ms 48332 KB Output is correct
16 Correct 162 ms 47908 KB Output is correct
17 Correct 184 ms 47964 KB Output is correct
18 Correct 201 ms 49744 KB Output is correct
19 Correct 169 ms 49744 KB Output is correct
20 Correct 230 ms 51780 KB Output is correct
21 Correct 131 ms 47636 KB Output is correct
22 Correct 143 ms 47292 KB Output is correct
23 Correct 210 ms 47308 KB Output is correct
24 Correct 177 ms 49368 KB Output is correct
25 Correct 182 ms 52132 KB Output is correct
26 Correct 143 ms 47900 KB Output is correct
27 Correct 157 ms 47416 KB Output is correct
28 Correct 158 ms 47432 KB Output is correct
29 Correct 186 ms 48852 KB Output is correct
30 Correct 206 ms 50252 KB Output is correct
31 Correct 135 ms 47796 KB Output is correct
32 Correct 154 ms 47512 KB Output is correct
33 Correct 183 ms 47504 KB Output is correct
34 Correct 200 ms 49372 KB Output is correct
35 Correct 196 ms 52076 KB Output is correct
36 Correct 171 ms 49508 KB Output is correct