Submission #344281

#	Time	Username	Problem	Language	Result	Execution time	Memory
344281		jenkinsser	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1024 ms	54296 KiB

plan

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define N 100005
#define INF 1e9+5
#define sp " "
#define endl "\n"
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define all(x) (x).begin(),(x).end()
#define ll long long
#define int ll
using namespace std;

int n,m,dan[N],k,q,par[N],vis[N],ans[N];
vector<pii> g[N];
set<int> s[N];
set<pii> st;
bool flag;

int get_parent(int u){
    if(par[u]==u) return u;
    return par[u]=get_parent(par[u]);
}

void solve(int u,int v){
    int U=get_parent(u);
    int V=get_parent(v);
    if(U==V){
        return;
    }
    if(s[U].size()>s[V].size()){
        swap(U,V);
    }
    par[U]=V;
    while(s[U].size()!=0){
        int cur= *(s[U].begin());
        s[U].erase(s[U].begin());
        flag=s[V].erase(cur);
        if(flag){
            ans[cur]=dan[v];
        }
        else{
            s[V].insert(cur);
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        dan[i]=INF;
        par[i]=i;
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        g[u].pb(mp(v,w));
        g[v].pb(mp(u,w));
    }
    cin >> k;
    for(int i=1;i<=k;i++){
        int x;
        cin >> x;
        dan[x]=0;
        st.insert({0,x});
    }

    while(!st.empty()){
        int cur=(st.begin()->nd);
        st.erase(st.begin());
        for(int i=0;i<g[cur].size();i++){
            int nei=g[cur][i].st;
            int edge=g[cur][i].nd;
            if(dan[nei]>dan[cur]+edge){
                st.erase({dan[nei],nei});
                dan[nei]=dan[cur]+edge;
                st.insert({dan[nei],nei});
            }
        }
    }
    cin >> q;
    for(int i=1;i<=q;i++){
        int u,v;
        cin >> u >> v;
        s[u].insert(i);
        s[v].insert(i);
    }
    vector<pii> vec;
    for(int i=1;i<=n;i++){
        vec.pb(mp(dan[i],i));
    }
    sort(vec.begin(),vec.end());
    for(int i=n-1;i>=0;i--){
        int cur=vec[i].nd;
        for(int j=0;j<g[cur].size();j++){
            int nei=g[cur][j].st;
            if(dan[nei]>=dan[cur])
                solve(nei,cur);
        }
    }
    for(int i=1;i<=q;i++){
        cout << ans[i] << endl;
    }
}

Compilation message (stderr)

plan.cpp: In function 'int32_t main()':
plan.cpp:75:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i=0;i<g[cur].size();i++){
      |                     ~^~~~~~~~~~~~~~
plan.cpp:99:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j=0;j<g[cur].size();j++){
      |                     ~^~~~~~~~~~~~~~

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