Submission #898801

#TimeUsernameProblemLanguageResultExecution timeMemory
898801vjudge1Valley (BOI19_valley)C++17
59 / 100
3048 ms19840 KiB
//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimization("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 1e5 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;

struct edge{
    int u , w , id;
};
struct hoom{
    int u , v , w ;
};
int n , s , q , e , dis[maxn] , t , st[maxn] , fn[maxn];
vector<edge> adj[maxn];
vector<hoom> ed;
vector<int> shop;
bool mark[maxn];

void Dfs(int v , int par){
    st[v] = ++t;
    for(auto u : adj[v]){
        if(u.u != par) Dfs(u.u , v);
    }
    fn[v] = t;
}

void Sub3(int kh , int ja){

    int u = ed[kh].u , v = ed[kh].v , w = ed[kh].w;
    if(st[v] < st[u]) swap(u , v);
    int f1 = (st[e] >= st[v] and fn[e] <= fn[v] ? 1 : 0);
    int f2 = (st[ja] >= st[v] and fn[ja] <= fn[v] ? 1 : 0);
    if(f1 == f2) cout << "escaped\n";
    else cout << 0 << '\n';
}

void Dijkstra(int kharab){
    set<pii> s;
    fill(dis , dis+maxn , INF);
    for(int u : shop) s.insert({0 , u}) , dis[u] = 0;
    while(!s.empty()){
        int v = (*s.begin()).S;
        s.erase(s.begin());
        for(auto u : adj[v]){
            if(u.id == kharab) continue;
            if(dis[u.u] > dis[v] + u.w) {
                s.erase({dis[u.u] , u.u});
                dis[u.u] = dis[v] + u.w;
                s.insert({dis[u.u] , u.u});
            }
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);

    cin >> n >> s >> q >> e;
    ed.pb({0,0,0});
    for(int i = 1 ; i < n ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w, i});
        adj[v].pb({u, w, i});
        ed.pb({u , v,  w});
    }
    for(int i = 1 ; i <= s ; i++){
        int x;
        cin >> x;
        shop.pb(x);
    }
    Dfs(1 , 0);
    while(q--){
        int kharab , ja;
        cin >> kharab >> ja;
        if(s == n) {
            Sub3(kharab , ja);
            continue;
        }
        Dijkstra(kharab);
        int u = ed[kharab].u , v = ed[kharab].v , w = ed[kharab].w;
        if(st[v] < st[u]) swap(u , v);
        int f1 = (st[e] >= st[v] and fn[e] <= fn[v] ? 1 : 0);
        int f2 = (st[ja] >= st[v] and fn[ja] <= fn[v] ? 1 : 0);
        if(f1 == f2) cout << "escaped\n";
        else {
            if(dis[ja] == INF) cout << "oo\n";
            else cout << dis[ja] << '\n';
        }
    }
}

Compilation message (stderr)

valley.cpp: In function 'void Sub3(long long int, long long int)':
valley.cpp:40:39: warning: unused variable 'w' [-Wunused-variable]
   40 |     int u = ed[kh].u , v = ed[kh].v , w = ed[kh].w;
      |                                       ^
valley.cpp: In function 'int32_t main()':
valley.cpp:92:51: warning: unused variable 'w' [-Wunused-variable]
   92 |         int u = ed[kharab].u , v = ed[kharab].v , w = ed[kharab].w;
      |                                                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...