oj.uz

Submission #245447

# Submission time Handle Problem Language Result Execution time Memory
245447 2020-07-06T13:14:54 Z uacoder123 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 3968 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
lli dis[3][201][201];
vector<ii> al[201];
int p[2][201][201]={};
lli arr[201][201],arr1[201][201];
lli n,m;
vi ap[2];
void floyd(lli t,lli e)
{
  if(e>1)
    floyd(t,e-1);
  for(lli i=1;i<=n;++i)
  {
    for(lli j=1;j<=n;++j)
    {
      arr1[i][j]=arr[i][j];
      for(lli k=0;k<al[i].size();++k)
      {
        if(t==1&&p[0][i][k]==1)
          arr1[i][j]=1000000000000000000;
        if(t==2&&p[1][i][k]==1)
          arr1[i][j]=1000000000000000000;
        arr1[i][j]=min(arr1[i][j],al[i][k].S+arr[al[i][k].F][j]);
      }
    }
  }
  swap(arr,arr1);
  if(e==n-1)
  {
    for(lli i=1;i<=n;++i)
      for(lli j=1;j<=n;++j)
        dis[t][i][j]=arr[i][j];
  }
}
void dij(lli t,lli so,lli te)
{
  lli d[201];
  ii lu[201];
  for(lli i=0;i<201;++i)
  {
    lu[i]=mp(0,0);
    d[i]=1000000000000000000;
  }
  set<ii> s;
  s.insert(mp(0,so));
  lu[so]=mp(so,0);
  while(s.size()!=0)
  {
    ii v=(*s.begin());
    d[v.S]=v.F;
    s.erase(s.begin());
    for(lli i=0;i<al[v.S].size();++i)
    {
      if(d[al[v.S][i].F]>al[v.S][i].S+v.F)
      {
       s.erase(mp(d[al[v.S][i].F],al[v.S][i].F));
       d[al[v.S][i].F]=al[v.S][i].S+v.F;
       lu[al[v.S][i].F]=mp(v.S,i);
       s.insert(mp(d[al[v.S][i].F],al[v.S][i].F)); 
      }
    }
  }
  if(lu[te].F!=0)
  {
    while(te!=so)
    {
      ap[t].pb(te);
      p[t][lu[te].F][lu[te].S]=1;
      te=lu[te].F;
    }
    ap[t].pb(so);
    }
  reverse(all(ap[t]));
}
void set1(int t)
{
  for(lli i=1;i<=n;++i)
      {
        for(lli j=1;j<=n;++j)
        {
          if(i==j)
            arr[i][j]=0;
          else
            arr[i][j]=1000000000000000000;
          dis[t][i][j]=1000000000000000000;
        }
      }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli test=1;
  memset(dis,-1,sizeof(dis));
  for(;test>0;--test)
  {
    cin>>n>>m;
    lli d[n][n];
    for(lli i=0;i<m;++i)
    {
      lli f,s,w,k;
      cin>>f>>s>>w>>k;
      al[f].pb(mp(s,w));
      d[f][s]=k;
    }
    dij(0,1,n);
    dij(1,n,1);
    set1(0);
    floyd(0,n);
    set1(1);
    floyd(1,n);
    set1(2);
    floyd(2,1);
    lli ans=dis[0][1][n]+dis[0][n][1];
    for(lli i=1;i<=n;++i)
    {
      for(lli j=0;j<al[i].size();++j)
      {
        lli ans1=dis[0][1][n],ans2=dis[0][n][1];
        if(p[0][i][j]!=1)
          ans1=min(ans1,al[i][j].S+dis[0][1][al[i][j].F]+dis[0][i][n]);
        else
        {
          ans1=1000000000000000000;
          for(lli k=0;k<=n-1;++k)
          {
            for(lli l=ap[0].size()-1;l>=0;--l)
            {
              ans1=min(ans1,dis[0][1][ap[0][k]]+dis[1][ap[0][k]][ap[0][l]]+dis[0][ap[0][l]][n]);
              if(al[i][j].F==ap[0][l])
                break;
            }
            if(ap[0][k]==i)
              break;
          }
        }
        if(p[1][i][j]!=1)
          ans2=min(ans2,al[i][j].S+dis[0][n][al[i][j].F]+dis[0][i][1]);
        else
        {
          ans2=1000000000000000000;
          for(lli k=0;k<=n-1;++k)
          {
            for(lli l=ap[1].size()-1;l>=0;--l)
            {
              ans2=min(ans2,dis[0][n][ap[1][k]]+dis[2][ap[1][k]][ap[1][l]]+dis[0][ap[1][l]][1]);
              if(al[i][j].F==ap[1][l])
                break;
            }
            if(ap[1][k]==i)
              break;
          }
        }
        ans=min(ans,ans1+ans2+d[i][al[i][j].F]);
      }
    }
    if(ans>=1000000000000000000)
      cout<<"-1"<<endl;
    else
    cout<<ans<<endl;
  }
  return(0);
}

Compilation message

ho_t4.cpp: In function 'void floyd(lli, lli)':
ho_t4.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(lli k=0;k<al[i].size();++k)
                   ~^~~~~~~~~~~~~
ho_t4.cpp: In function 'void dij(lli, lli, lli)':
ho_t4.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(lli i=0;i<al[v.S].size();++i)
                 ~^~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:132:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(lli j=0;j<al[i].size();++j)
                   ~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 2432 KB Output is correct
2 Correct 88 ms 2304 KB Output is correct
3 Correct 232 ms 2304 KB Output is correct
4 Correct 237 ms 2424 KB Output is correct
5 Runtime error 19 ms 3968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 3576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 2424 KB Output is correct
2 Correct 81 ms 2424 KB Output is correct
3 Execution timed out 1095 ms 3192 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 2432 KB Output is correct
2 Correct 88 ms 2304 KB Output is correct
3 Correct 232 ms 2304 KB Output is correct
4 Correct 237 ms 2424 KB Output is correct
5 Runtime error 19 ms 3968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -