제출 #1022448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022448		hasan2006	Evacuation plan (IZhO18_plan)	C++17	0 / 100	296 ms	46928 KiB

plan

#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define int long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e5 + 9 , mod = 1e9 + 7;
ll   a[N];
ll n , m , q , k;

vector<pair<int,int>>v[N];
set<pair<int,int>>st;

void dijkstra(){
    while(st.size()){
        auto it = st.begin();
        ll x = it->se;
        ll y = it->fi;
        st.erase(it);
        if(a[x] != y)
            continue;
        for(auto to : v[x]){
            if(a[x] + to.se < a[to.fi]){
                a[to.fi] = a[x] + to.se;
                st.insert({a[to.fi] , to.fi});
            }
        }
    }
}

ll sz[N] , p[N] , mn[N];

int get(int n) {
    while(p[n] != n)
        n = p[n];
	return p[n];
}

void join(int x , int y , int k){
    x = get(x);
    y = get(y);
    if(x != y){
        if(sz[x] < sz[y])
            swap(x , y);
        p[y] = x;
        mn[y] = k;
        sz[x] += sz[y];
    }
}

void get1(int x , int y){
    while(true){
        if(sz[x] < sz[y]){
            if(p[x] == y){
                cout<<mn[x]<<"\n";
                return;
            }
            x = p[x];
        }else{
            if(p[y] == x){
                cout<<mn[y]<<"\n";
                return;
            }
            y = p[y];
        }
        if(x == y){
            cout<<0<<"\n";
            return;
        }
    }
}

void solve()
{
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int x , y , z;
        cin>>x>>y>>z;
        v[x].pb({y , z});
        v[y].pb({x , z});
    }
    cin>>k;
    for(int i = 1; i <= n; i++){
        a[i] = 1e9;
    }
    while(k--){
        int x;
        cin>>x;
        a[x] = 0;
        st.insert({0 , x});
    }
    dijkstra();
    vector<pair<int,int>>g;
    for(int i = 1; i <= n; i++){
        p[i] = i;
        sz[i] = 1;
        g.push_back({a[i] , i});
    }
    sort(rall(g));
    for(auto i : g){
        for(auto to : v[i.se]){
            if(a[to.fi] >= a[i.se]){
                join(i.se , to.fi , a[i.se]);
            }
        }
    }
    cin>>q;
    while(q--){
        int x , y;
        cin>>x>>y;
        get1(x , y);
    }
}

signed main(){
    TL;
/*    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
int t = 1;
//cin>>t;
while(t--)
     {
     solve();
     }
}
// Author : حسن

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp: In function 'long long int get(long long int)':
plan.cpp:49:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   49 |     while(p[n] != n)
      |     ^~~~~
plan.cpp:51:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   51 |  return p[n];
      |  ^~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46