oj.uz

Submission #547665

# Submission time Handle Problem Language Result Execution time Memory
547665 2022-04-11T09:42:42 Z Soul234 Valley (BOI19_valley) C++14
100 / 100
 203 ms 37060 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

#define f first
#define s second

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a = b, 1 : 0;
}
const int MX = 1e5+5, LG = 17;
const ll INF = 1e18;
int N, S, Q, E, jmp[MX][LG], tin[MX], tout[MX], timer_;
ll dp[MX], mnjmp[MX][LG], dep[MX];
pi eds[MX];
V<pi> adj[MX];

void dfs(int u, int p) {
    tin[u] = ++timer_;
    if(dp[u] == -1) dp[u] = dep[u];
    each(v, adj[u]) if(v.f != p) {
        dep[v.f] = dep[u] + v.s;
        dfs(v.f, u);
        ckmin(dp[u], dp[v.f]);
    }
    tout[u] = timer_;
}

void DFS(int u, int p) {
    mnjmp[u][0] = min(dp[u], dp[p]);
    FOR(i,1,LG) {
        jmp[u][i] = jmp[jmp[u][i-1]][i-1];
        mnjmp[u][i] = min(mnjmp[u][i-1], mnjmp[jmp[u][i-1]][i-1]);
    }
    each(v, adj[u]) if(v.f != p) {
        jmp[v.f][0] = u;
        DFS(v.f, u);
    }
}

bool isa(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }

void solve() {
    cin>>N>>S>>Q>>E;
    memset(dp, 0x3f, sizeof dp);
    memset(mnjmp, 0x3f, sizeof mnjmp);
    F0R(_,N-1) {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
        eds[_+1] = {u,v};
    }
    F0R(i,S) {
        int x; cin>>x;
        dp[x] = -1;
    }
    //dbg(N);
    dfs(E, -1);
    FOR(i,1,N+1) dp[i] -= 2*dep[i];
    jmp[E][0] = E;
    DFS(E,E);
    //dbg(dp[3]);
    while(Q-->0) {
        int I, R; cin>>I>>R;
        int x = eds[I].f, y = eds[I].s;
        if(dep[x] > dep[y]) swap(x,y);
        if(isa(y, R)) {
            ll ans = dp[R];
            int cur = R;
            R0F(i,LG) if(isa(y,jmp[R][i])) ckmin(ans, mnjmp[R][i]), R = jmp[R][i];
            if(ans>=INF) {
                cout << "oo\n";
                continue;
            }
            cout << ans + dep[cur] << nl;
        }
        else {
            cout << "escaped\n";
        }
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

valley.cpp: In function 'void setIO(std::string)':
valley.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16852 KB Output is correct
2 Correct 9 ms 16900 KB Output is correct
3 Correct 9 ms 16900 KB Output is correct
4 Correct 10 ms 16896 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16852 KB Output is correct
2 Correct 9 ms 16900 KB Output is correct
3 Correct 9 ms 16900 KB Output is correct
4 Correct 10 ms 16896 KB Output is correct
5 Correct 8 ms 16852 KB Output is correct
6 Correct 11 ms 16876 KB Output is correct
7 Correct 9 ms 16852 KB Output is correct
8 Correct 9 ms 16852 KB Output is correct
9 Correct 9 ms 16900 KB Output is correct
10 Correct 11 ms 16904 KB Output is correct
11 Correct 9 ms 16896 KB Output is correct
12 Correct 9 ms 16852 KB Output is correct
13 Correct 9 ms 16852 KB Output is correct
14 Correct 10 ms 16904 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 34160 KB Output is correct
2 Correct 172 ms 33876 KB Output is correct
3 Correct 146 ms 33716 KB Output is correct
4 Correct 169 ms 35252 KB Output is correct
5 Correct 195 ms 35412 KB Output is correct
6 Correct 182 ms 36812 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16852 KB Output is correct
2 Correct 9 ms 16900 KB Output is correct
3 Correct 9 ms 16900 KB Output is correct
4 Correct 10 ms 16896 KB Output is correct
5 Correct 8 ms 16852 KB Output is correct
6 Correct 11 ms 16876 KB Output is correct
7 Correct 9 ms 16852 KB Output is correct
8 Correct 9 ms 16852 KB Output is correct
9 Correct 9 ms 16900 KB Output is correct
10 Correct 11 ms 16904 KB Output is correct
11 Correct 9 ms 16896 KB Output is correct
12 Correct 9 ms 16852 KB Output is correct
13 Correct 9 ms 16852 KB Output is correct
14 Correct 10 ms 16904 KB Output is correct
15 Correct 136 ms 34160 KB Output is correct
16 Correct 172 ms 33876 KB Output is correct
17 Correct 146 ms 33716 KB Output is correct
18 Correct 169 ms 35252 KB Output is correct
19 Correct 195 ms 35412 KB Output is correct
20 Correct 182 ms 36812 KB Output is correct
21 Correct 169 ms 33528 KB Output is correct
22 Correct 134 ms 33264 KB Output is correct
23 Correct 149 ms 33196 KB Output is correct
24 Correct 162 ms 34792 KB Output is correct
25 Correct 203 ms 37060 KB Output is correct
26 Correct 123 ms 33620 KB Output is correct
27 Correct 124 ms 33208 KB Output is correct
28 Correct 179 ms 33144 KB Output is correct
29 Correct 160 ms 34300 KB Output is correct
30 Correct 182 ms 35544 KB Output is correct
31 Correct 138 ms 33652 KB Output is correct
32 Correct 129 ms 33396 KB Output is correct
33 Correct 150 ms 33400 KB Output is correct
34 Correct 196 ms 34960 KB Output is correct
35 Correct 162 ms 37004 KB Output is correct
36 Correct 177 ms 34892 KB Output is correct