oj.uz

Submission #705479

# Submission time Handle Problem Language Result Execution time Memory
705479 2023-03-04T13:23:01 Z epicci23 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 53 ms 5336 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)1e15;
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;

multiset<array<int,4>> git;
vector<array<int,4>> edge;

multiset<array<int,3>> v[205];

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];
    }
  }
  else
  {
    int xd=1;
    if(vis[1]==0) return;
    while(xd!=n)
    {
      git.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<=201;i++) for(int j=1;j<=201;j++) dist[i][j]=INF;
  for(int i=1;i<=201;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(v[x[0]].find({x[1],x[2],x[3]}));
      v[x[1]].insert({x[0],x[2],x[3]});
      gitme=min(gitme,dijk(1));
      gelme=min(gelme,dijk(n));
      v[x[1]].erase(v[x[1]].find({x[0],x[2],x[3]}));
      v[x[0]].insert({x[1],x[2],x[3]});
      ans=min(ans,gitme+gelme+x[3]);
    }
    else
    {
      gitme=min(gitme,dist[1][n]);
      gitme=min(gitme,dist[1][x[1]]+dist[x[0]][n]+x[2]+x[3]);
      gelme=min(gelme,dist[n][1]);
      gelme=min(gelme,dist[n][x[1]]+x[2]+x[3]+dist[x[0]][1]);
      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;//t=in();
 
   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 13 ms 724 KB Output is correct
2 Correct 8 ms 596 KB Output is correct
3 Correct 10 ms 748 KB Output is correct
4 Correct 11 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 8 ms 680 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 18 ms 780 KB Output is correct
11 Correct 46 ms 724 KB Output is correct
12 Correct 38 ms 724 KB Output is correct
13 Incorrect 8 ms 752 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5220 KB Output is correct
2 Correct 53 ms 5288 KB Output is correct
3 Correct 52 ms 5336 KB Output is correct
4 Correct 11 ms 848 KB Output is correct
5 Correct 11 ms 752 KB Output is correct
6 Correct 8 ms 728 KB Output is correct
7 Correct 8 ms 700 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Incorrect 35 ms 5316 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 752 KB Output is correct
2 Correct 9 ms 596 KB Output is correct
3 Correct 39 ms 4680 KB Output is correct
4 Correct 8 ms 680 KB Output is correct
5 Correct 44 ms 5244 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Incorrect 43 ms 5264 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 724 KB Output is correct
2 Correct 8 ms 596 KB Output is correct
3 Correct 10 ms 748 KB Output is correct
4 Correct 11 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 8 ms 680 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 18 ms 780 KB Output is correct
11 Correct 46 ms 724 KB Output is correct
12 Correct 38 ms 724 KB Output is correct
13 Incorrect 8 ms 752 KB Output isn't correct
14 Halted 0 ms 0 KB -