Submission #565603

#	Time	Username	Problem	Language	Result	Execution time	Memory
565603		Uzouf	Evacuation plan (IZhO18_plan)	C++14	54 / 100	4018 ms	97936 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=105;//2e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

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;
    vector<vector<pair<int,int> > > v(n+5);
    map<pair<int,int>,bool> con;
    while (m--) {
      int a,b,c; cin>>a>>b>>c;
      con[{a,b}]=true; con[{b,a}]=true;
      v[a].push_back({c,b});
      v[b].push_back({c,a});
    }

    int k; cin>>k;
    int npp[k];
    for (int &i:npp) cin>>i;

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

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

    while (!q.empty())
    {
        int cnt=q.top().first;
        int node=q.top().second;
        q.pop();
        if (dis[node]<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]>(cnt+price))
            {
                dis[child]=(cnt+price);
                q.push({dis[child],child});
            }
        }
    }

    //for (int i=1;i<=n;i++) cout<<dis[i]<<' ';

    int t; cin>>t;
    while (t--) {
      int a,b; cin>>a>>b;

      if (con[{a,b}]) {cout<<min(dis[a],dis[b])<<endl; continue;}

      int dis2[n+5];
      for (int i=0;i<n+5;i++) {
        dis2[i]=0;
      }
      priority_queue<pair<int,int> >q2;

      dis2[a]=dis[a]; q2.push({dis[a],a});

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

      cout<<dis2[b]<<endl;
    }

}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:48: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]
   48 |         for (int i=0;i<v[node].size();i++)
      |                      ~^~~~~~~~~~~~~~~
plan.cpp:82:25: 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]
   82 |           for (int i=0;i<v[node].size();i++)
      |                        ~^~~~~~~~~~~~~~~

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