Submission #710802

#	Time	Username	Problem	Language	Result	Execution time	Memory
710802		epicci23	Robot (JOI21_ho_t4)	C++17	100 / 100	1174 ms	65420 KiB

Main

#include "bits/stdc++.h"
#pragma optimize ("Bismillahirrahmanirrahim")
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n" 
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
//#define m (l+r)/2
constexpr int N=200005;
constexpr int MOD=1000000007;
constexpr int  INF2 = LLONG_MAX;
constexpr int INF=(int)1e18;
constexpr int LOG=30;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//to think//
/*
 * graph approach
 * dp
 * dividing the problem to smaller statements
 * finding the real constraint
 * sqrt decomposition
 * greedy approach
 * pigeonhole principle
 * rewriting the problem/equality 
 * bitwise approaches
 * binary search if monotonic
 * divide and conquer
 * combinatorics
 * inclusion - exclusion
 * think like bfs
*/



inline int in()
{
  int x;cin >> x;
  return x;
}

inline string in2()
{
  string x;cin >> x;
  return x;
}


void solve()
{
  int n=in(),m=in();

  map<int,pii> mp[n+2];
  vector<array<int,2>> vis(n+2,{0,0});
  vector<array<int,3>> v[n+2];
  int dist[n+2][2];
  dist[1][1]=0;
  for(int i=2;i<=n;i++) dist[i][0]=dist[i][1]=INF; 
 

  for(int i=1;i<=m;i++)
  {
    int a=in(),b=in(),c=in(),d=in();
    v[a].pb({b,c,d});
    v[b].pb({a,c,d});
    mp[a][c].ff+=d;
    mp[b][c].ff+=d;
    mp[b][c].ss++;
    mp[a][c].ss++;
  }

  priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> pq;

  pq.push({0,1,INF,INF});
  while(!pq.empty())
  {
    array<int,4> c=pq.top();pq.pop();
    
    map<int,int> mp2;
    if(c[2]==INF)
    {
      if(vis[c[1]][1]) continue;
      vis[c[1]][1]=1;
    }
    else
    {
      if(vis[c[1]][0]) continue;
      vis[c[1]][0]=1; 
    }
   // cout << c[0] << " " << c[1] << " " << c[2] << " " << c[3] << endl;
    
    for(auto x:v[c[1]]) mp2[x[1]]=INF;

    for(auto x:v[c[1]])
    {
      if(vis[x[0]][0] || vis[x[0]][1]) mp2[x[1]]=min({mp2[x[1]],dist[x[0]][0],dist[x[0]][1]});
    }

    for(auto x:v[c[1]])
    {
      if(mp[c[1]][x[1]].ss==1)
      {
        if(c[0]<dist[x[0]][1])
        {
          dist[x[0]][1]=c[0];
          pq.push({c[0],x[0],INF,INF});
        }
      }
      if(c[0]+x[2]<dist[x[0]][0])
      {
        dist[x[0]][0]=c[0]+x[2];
        pq.push({c[0]+x[2],x[0],x[1],x[2]});
      }
    }
    for(auto x:v[c[1]])
    {
      if(c[0]+mp[c[1]][x[1]].ff-x[2]-(c[2]==x[1] ? c[3] : 0) < dist[x[0]][1])
      {
        dist[x[0]][1]=c[0]+mp[c[1]][x[1]].ff-x[2];
        pq.push({c[0]+mp[c[1]][x[1]].ff-x[2],x[0],INF,INF});
      }
    }

    for(auto x:v[c[1]])
    {
      if(dist[x[0]][1] > mp2[x[1]] + mp[c[1]][x[1]].ff - x[2])
      {
        dist[x[0]][1]= mp2[x[1]] + mp[c[1]][x[1]].ff - x[2];
        pq.push({dist[x[0]][1],x[0],INF,INF});
      }
    }
    
  }
  cout << ( (dist[n][1]==INF && dist[n][0]==INF) ? -1 : min(dist[n][1],dist[n][0])) << endl;
}

int32_t main(){
   

     cin.tie(0); ios::sync_with_stdio(0);
     cout << fixed <<  setprecision(15);
   
   int t=1;//cin>> t;
 
 for(int i=1;i<=t;i++)
 {
  //  cout << "Case #" << i << ": ";
    solve();
 }
 
 return 0;
}

Compilation message (stderr)

Main.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("Bismillahirrahmanirrahim")
      |

• Subtask 1: 34 / 34
• Subtask 2: 24 / 24
• Subtask 3: 42 / 42