Submission #168526

#	Time	Username	Problem	Language	Result	Execution time	Memory
168526		achibasadzishvili	Evacuation plan (IZhO18_plan)	C++14	100 / 100	835 ms	33196 KiB

plan

#include <bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
ll k,n,m,qq,d[100005],p[100005],c[100005],ans[100005],las,fix[100005];
ll qu[100005],sz[100005];
vector<ll>vec[100005];
vector<pair<ll,ll> >v[100005],q[100005];
set<pair<ll,ll> >st;
ll find(ll x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}
void join(ll x,ll y){
    x = find(x);
    y = find(y);
    if(x == y)return;
    if(qu[x] < qu[y])swap(x , y);
    qu[x] += qu[y];
    sz[x] += sz[y];
    for(int i=0; i<q[y].size(); i++){
        if(find(q[y][i].f) == x)
            ans[q[y][i].s] = min(ans[q[y][i].s] , las);
        q[x].pb(q[y][i]);
    }
    p[y] = x;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
 
    for(int i=1; i<=m; i++){
        int x,y,z;
        cin >> x >> y >> z;
        v[x].pb(mp(y , z));
        v[y].pb(mp(x , z));
    }
 
    cin >> k;
 
    for(int i=1; i<=n; i++){
        d[i] = 1000000000;
    }
 
    for(int i=1; i<=k; i++){
        cin >> c[i];
        st.insert(mp(0LL , c[i]));
        d[c[i]] = 0;
    }
 
    while(st.size()){
        ll x = (*st.begin()).s;
        st.erase(st.begin());
        for(int i=0; i<v[x].size(); i++){
            ll to = v[x][i].f;
            if(d[to] > d[x] + v[x][i].s){
                if(st.find(mp(d[to] , to)) != st.end())st.erase(st.find(mp(d[to] , to)));
                d[to] = d[x] + v[x][i].s;
                st.insert(mp(d[to] , to));
            }
        }
    }
 
    cin >> qq;
 
    for(int i=1; i<=qq; i++){
        ans[i] = 1000000000;
        int x,y;
        cin >> x >> y;
        q[x].pb(mp(y , i));
        q[y].pb(mp(x , i));
    }
 
    vector<pair<ll,ll> >g;
 
    for(int i=1; i<=n; i++){
        g.pb(mp(d[i] , i));
    }
 
 
    sort(g.begin() , g.end());
    reverse(g.begin() , g.end());
 
    for(int i=1; i<=n; i++){
        p[i] = i;
        qu[i] = (int)q[i].size();
        vec[i].pb(i);
        sz[i] = 1;
    }
 
    for(int i=0; i<g.size(); i++){
        las = g[i].f;
        fix[g[i].s] = 1;
        for(int j=0; j<v[g[i].s].size(); j++){
            ll to = v[g[i].s][j].f;
            if(fix[to] == 1){
                join(g[i].s , to);
            }
        }
    }
 
 
    for(int i=1; i<=qq; i++)
        cout << ans[i] << '\n';
 
 
 
 
 
    return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'void join(int, int)':
plan.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<q[y].size(); i++){
                  ~^~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v[x].size(); i++){
                      ~^~~~~~~~~~~~
plan.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<g.size(); i++){
                  ~^~~~~~~~~
plan.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[g[i].s].size(); j++){
                      ~^~~~~~~~~~~~~~~~~

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