Submission #347768

#	Time	Username	Problem	Language	Result	Execution time	Memory
347768		Dymo	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1522 ms	60140 KiB

plan

#include<bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb    push_back
#define eb   emplace_back
#define ll    long long
//#define ull unsigned long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=5e5+54;
const ll mod =2520   ;
const ll base=1e18;
ll dp[maxn];
vector<pll> adj[maxn];
priority_queue<pll,vector<pll>,greater<pll>> q;

void dosth()
{
   while (!q.empty())
   {
       auto p=q.top();
       q.pop();
       if (dp[p.ss]!=p.ff) continue;
       ll u=p.ss;
       for (auto to:adj[u])
       {
           if (dp[to.ff]>dp[u]+to.ss)
           {
               dp[to.ff]=dp[u]+to.ss;
               q.push(make_pair(dp[to.ff],to.ff));
           }
       }
   }
}
pll a[maxn];
ll l[maxn];
ll r[maxn];
bool dd[maxn];
ll par[maxn];
ll find_par(ll u)
{
    if (u==par[u]) return u;
    return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return ;
    par[x]=y;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, m;
     cin>>n >> m;
     for (int i=1;i<=m;i++)
     {
         ll x, y, w;
          cin>> x>> y>> w;
          adj[x].pb(make_pair(y,w));
          adj[y].pb(make_pair(x,w));

     }
     for (int i=1;i<=n;i++)
     {
         dp[i]=1e15;
     }
     ll k;
      cin>> k;
      for (int i=1;i<=k;i++)
      {
          ll x;
           cin>> x;
           dp[x]=0;
           q.push(make_pair(dp[x],x));
      }
      dosth();
      ll q;
       cin>> q;
       for (int i=1;i<=q;i++)
       {
          cin>>a[i].ff>>a[i].ss;
       }
       vector<pll> b;
       ll mx=0;
       for (int i=1;i<=n;i++)
       {
           mx=max(mx,dp[i]);
           b.pb(make_pair(dp[i],i));
       }
       sort(b.rbegin(),b.rend());
       for (int i=1;i<=q;i++)
       {
           l[i]=0;
           r[i]=mx;
       }
       while (1)
       {
           for (int i=1;i<=n;i++) dd[i]=0, par[i]=i ;

           vector<pair<ll,ll>> gr;
           for (int i=1;i<=q;i++)
           {
               if (l[i]<=r[i])
               {
                   gr.pb(make_pair((l[i]+r[i])/2,i));
               }
           }
           if (gr.size())
           {
               sort(gr.rbegin(),gr.rend());
           }
           else break;
           ll idnw=0;
           for (auto p:gr)
           {
               ll val=p.ff;
               while (idnw<b.size()&&val<=b[idnw].ff)
               {
                   dd[b[idnw].ss]=1;
                   ll u=b[idnw].ss;
                   for (auto to:adj[u])
                   {
                       if (dd[to.ff])
                       {
                           dsu(to.ff,u);
                       }
                   }
                   idnw++;
               }
               ll x=a[p.ss].ff;
               ll y=a[p.ss].ss;
               if (find_par(x)==find_par(y))
               {
                   l[p.ss]=val+1;
               }
               else
               {
                   r[p.ss]=val-1;
               }
           }

       }
       for (int i=1;i<=q;i++)
       {
           cout <<r[i]<<endl;
       }

/*
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:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
plan.cpp:7: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
plan.cpp: In function 'int main()':
plan.cpp:132:27: 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]
  132 |                while (idnw<b.size()&&val<=b[idnw].ff)
      |                       ~~~~^~~~~~~~~
plan.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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