oj.uz

Submission #705452

# Submission time Handle Problem Language Result Execution time Memory
705452 2023-03-04T12:10:13 Z epicci23 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 63 ms 14664 KB 
#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;
}

/*
 1- sp route cikar (n^2 dijkstra ile)
 2- sp routetaki her edge için tekrardan dijkstra(n^2) at
 3- sp routetaki edge değilse dist[1][b] + c + d dist[a][n] dene
*/

int n,m;

set<array<int,4>> git,gel;
vector<array<int,4>> edge;

set<array<int,3>> v[N];

int dijk(int rt)
{
  int di[n+2];
  bool vis[n+2];

  for(int i=1;i<=n;i++) {di[i]=INF;vis[i]=0;}

  di[rt]=0;

  for(int i=1;i<=n;i++)
  {
    pii cur={INF,INF};
    for(int j=1;j<=n;j++) if(vis[j]==0) cur=min(cur,{di[j],j});
    if(cur.ff==INF) break;
    vis[cur.ss]=1;
    for(array<int,3> x:v[cur.ss]) if(cur.ff+x[1]<di[x[0]]) di[x[0]]=cur.ff+x[1];
  }
  
  if(rt==1) return di[n];
  else return di[1];
}

void rout(int rt)
{
  int di[n+1];
  bool vis[n+1];
  for(int i=1;i<=n;i++) {di[i]=INF;vis[i]=0;}
  di[rt]=0;
  
  array<int,3> par[n+1];

  for(int i=1;i<=n;i++)
  {
    pii cur={INF,INF};
    for(int j=1;j<=n;j++) if(vis[j]==0) cur=min(cur,{di[j],j});
    if(cur.ff==INF) break;
    vis[cur.ss]=1;
    for(array<int,3> x:v[cur.ss]) 
      if(cur.ff+x[1]<di[x[0]]) 
        {par[x[0]]={cur.ss,x[1],x[2]};di[x[0]]=cur.ff+x[1];}
  }
  

  if(rt==1)
  {
    if(vis[n]==0) return;
    int xd=n;
    while(xd!=1)
    {
      git.insert({par[xd][0],xd,par[xd][1],par[xd][2]});
      xd=par[xd][0];
      //cout << "xd: " << xd << endl;
    }
  }
  else
  {
    int xd=1;
    if(vis[1]==0) return;
    while(xd!=n)
    {
      gel.insert({par[xd][0],xd,par[xd][1],par[xd][2]});
      xd=par[xd][0];
    }
  }
}


int dist[202][202];

void solve()
{
  n=in(),m=in();
  for(int i=1;i<=200;i++) for(int j=1;j<=200;j++) dist[i][j]=INF;
  for(int i=1;i<=200;i++) dist[i][i]=0;
  
  for(int i=1;i<=m;i++)
  {
    int a=in(),b=in(),c=in(),d=in();
    edge.pb({a,b,c,d});
    dist[a][b]=min(dist[a][b],c);
    v[a].insert({b,c,d});
  }
  
  rout(1);
  rout(n);

  for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
  
   
  int ans=dist[1][n]+dist[n][1];
  for(array<int,4> x:edge)
  {
    int gitme=INF;
    int gelme=INF;

    if(git.count(x)==1)
    { 
      v[x[0]].erase({x[1],x[2],x[3]});
      v[x[1]].insert({x[0],x[2]+x[3],x[3]});
      gitme=min(gitme,dijk(1));
      v[x[1]].erase({x[0],x[2]+x[3],x[3]});
      v[x[0]].insert({x[1],x[2],x[3]});
    }
    else
    {
      gitme=min(gitme,dist[1][n]);
      gitme=min(gitme,dist[1][x[1]]+dist[x[0]][n]+x[2]+x[3]);
    }
    if(gel.count(x)==1)
    {
      v[x[0]].erase({x[1],x[2],x[3]});
      v[x[1]].insert({x[0],x[2]+x[3],x[3]});
      gelme=min(gelme,dijk(n));
      v[x[1]].erase({x[0],x[2]+x[3],x[3]});
      v[x[0]].insert({x[1],x[2],x[3]});
    }
    else
    {
      gelme=min(gelme,dist[n][1]);
      gelme=min(gelme,dist[n][x[1]]+dist[x[0]][1]+x[2]+x[3]);
    }
    ans=min(ans,gitme+gelme);
  }

  cout << (ans>=INF ? -1 :ans) << 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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10068 KB Output is correct
2 Correct 12 ms 9940 KB Output is correct
3 Correct 15 ms 10132 KB Output is correct
4 Correct 15 ms 10068 KB Output is correct
5 Correct 5 ms 10036 KB Output is correct
6 Correct 13 ms 9940 KB Output is correct
7 Correct 5 ms 10028 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 10044 KB Output is correct
10 Correct 52 ms 10068 KB Output is correct
11 Correct 63 ms 10068 KB Output is correct
12 Correct 55 ms 10148 KB Output is correct
13 Incorrect 13 ms 10068 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14632 KB Output is correct
2 Correct 50 ms 14612 KB Output is correct
3 Correct 57 ms 14652 KB Output is correct
4 Correct 20 ms 10152 KB Output is correct
5 Correct 17 ms 10136 KB Output is correct
6 Correct 16 ms 10068 KB Output is correct
7 Correct 14 ms 10084 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Incorrect 44 ms 14644 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10068 KB Output is correct
2 Correct 15 ms 10064 KB Output is correct
3 Correct 41 ms 14056 KB Output is correct
4 Correct 13 ms 9940 KB Output is correct
5 Correct 50 ms 14664 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Incorrect 43 ms 14612 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 10068 KB Output is correct
2 Correct 12 ms 9940 KB Output is correct
3 Correct 15 ms 10132 KB Output is correct
4 Correct 15 ms 10068 KB Output is correct
5 Correct 5 ms 10036 KB Output is correct
6 Correct 13 ms 9940 KB Output is correct
7 Correct 5 ms 10028 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 10044 KB Output is correct
10 Correct 52 ms 10068 KB Output is correct
11 Correct 63 ms 10068 KB Output is correct
12 Correct 55 ms 10148 KB Output is correct
13 Incorrect 13 ms 10068 KB Output isn't correct
14 Halted 0 ms 0 KB -