Submission #566004

#	Time	Username	Problem	Language	Result	Execution time	Memory
566004		Uzouf	Evacuation plan (IZhO18_plan)	C++14	100 / 100	508 ms	46264 KiB

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e9+7;
const int N=1e5+5;//2e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

vector<vector<pair<int,int> > > tst(N),v(N);
vector<vector<int> > grp(N);
pair<int,int> dis[N];
int npp[N],par[N],ans[N];
bool vis[N];

void con(int a,int b,int cst) {
  a=par[a]; b=par[b];
  if (grp[a].size()>grp[b].size()) swap(a,b);

  for (int i:grp[a]) {
    for (auto j=0;j<tst[i].size();j++) {
      if (par[tst[i][j].first]==b) ans[tst[i][j].second]=cst;
    }
  }

  for (int i:grp[a]) {
    par[i]=b; grp[b].push_back(i);
  }
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    int n,m; cin>>n>>m;
    while (m--) {
      int a,b,c; cin>>a>>b>>c;
      v[a].push_back({c,b});
      v[b].push_back({c,a});
    }

    int k; cin>>k;
    for (int i=0;i<k;i++) cin>>npp[i];

    for (int i=1;i<=n;i++) {
      dis[i]={1e10,i};
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;

    for (int i=0;i<k;i++) {
      dis[npp[i]]={0,npp[i]}; q.push({0,npp[i]});
    }

    while (!q.empty())
    {
        int cnt=q.top().first;
        int node=q.top().second;
        q.pop();
        if (dis[node].first<cnt) {continue;}
        for (int i=0;i<v[node].size();i++)
        {
            int price=v[node][i].first;
            int child=v[node][i].second;
            if (dis[child].first>(cnt+price))
            {
                dis[child].first=cnt+price;
                q.push(dis[child]);
            }
        }
    }

    int t; cin>>t;
    for (int i=0;i<t;i++) {
      int a,b; cin>>a>>b;
      tst[a].push_back({b,i});
      tst[b].push_back({a,i});
    }

    sort(dis,dis+N); reverse(dis,dis+N);
    for (int i=1;i<=n;i++) {
      par[i]=i; grp[i].push_back(i);
    }

    for (int i=0;i<n;i++) {
      int dd=dis[i].first,nm=dis[i].second;
      for (int j=0;j<v[nm].size();j++) {
        if (vis[v[nm][j].second] && par[v[nm][j].second]!=par[nm]) {
          con(nm,v[nm][j].second,dd);
        }
      }
      vis[nm]=true;
    }

    for (int i=0;i<t;i++) cout<<ans[i]<<endl;
}

Compilation message (stderr)

plan.cpp: In function 'void con(long long int, long long int, long long int)':
plan.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (auto j=0;j<tst[i].size();j++) {
      |                   ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:64:23: 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]
   64 |         for (int i=0;i<v[node].size();i++)
      |                      ~^~~~~~~~~~~~~~~
plan.cpp:90:21: 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]
   90 |       for (int j=0;j<v[nm].size();j++) {
      |                    ~^~~~~~~~~~~~~

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