Submission #898793

#	Time	Username	Problem	Language	Result	Execution time	Memory
898793		vjudge1	Misspelling (JOI22_misspelling)	C++17	0 / 100	8 ms	16728 KiB

misspelling

//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 = 2e5 + 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 Bfs(int kharab){
    queue<int> qu;
    fill(dis , dis+maxn , INF);
    memset(mark , false , sizeof mark);
    for(int u : shop) qu.push(u) , dis[u] = 0 , mark[u] = true;
    while(!qu.empty()){
        int v = qu.front();
        qu.pop();
        for(auto u : adj[v]){
            if(u.id == kharab or mark[u.u]) continue;
            mark[u.u] = true , dis[u.u] = dis[v] + u.w , qu.push(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;
        }
        Bfs(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)

misspelling.cpp: In function 'void Sub3(long long int, long long int)':
misspelling.cpp:40:39: warning: unused variable 'w' [-Wunused-variable]
   40 |     int u = ed[kh].u , v = ed[kh].v , w = ed[kh].w;
      |                                       ^
misspelling.cpp: In function 'int32_t main()':
misspelling.cpp:89:51: warning: unused variable 'w' [-Wunused-variable]
   89 |         int u = ed[kharab].u , v = ed[kharab].v , w = ed[kharab].w;
      |                                                   ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11