Submission #168529

#	Time	Username	Problem	Language	Result	Execution time	Memory
168529		achibasadzishvili	Evacuation plan (IZhO18_plan)	C++17	100 / 100	855 ms	32960 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;
inline ll find(ll x){
    if(p[x] == x)return x;
    return p[x] = find(p[x]);
}
inline 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(){
  scanf("%d%d",&n,&m);
 
    for(int i=1; i<=m; i++){
        int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
        v[x].pb(mp(y , z));
        v[y].pb(mp(x , z));
    }
    scanf("%d",&k);
 
    for(int i=1; i<=n; i++){
        d[i] = 1000000000;
    }
 
    for(int i=1; i<=k; i++){
        scanf("%d",&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));
            }
        }
    }
 
    scanf("%d",&qq);
 
    for(int i=1; i<=qq; i++){
        ans[i] = 1000000000;
        int x,y;
      scanf("%d%d",&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++)
      printf("%d ",ans[i]);
 
    return 0;
}

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:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<v[x].size(); i++){
                      ~^~~~~~~~~~~~
plan.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<g.size(); i++){
                  ~^~~~~~~~~
plan.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<v[g[i].s].size(); j++){
                      ~^~~~~~~~~~~~~~~~~
plan.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~
plan.cpp:36:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d",&x,&y,&z);
       ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k);
     ~~~~~^~~~~~~~~
plan.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c[i]);
         ~~~~~^~~~~~~~~~~~
plan.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&qq);
     ~~~~~^~~~~~~~~~
plan.cpp:70:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d",&x,&y);
       ~~~~~^~~~~~~~~~~~~~

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