oj.uz

Submission #245481

# Submission time Handle Problem Language Result Execution time Memory
245481 2020-07-06T14:05:18 Z uacoder123 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 3960 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]=10000000000000000;
        else if(t==2&&p[1][i][k]==1)
          arr1[i][j]=10000000000000000;
        else
        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]=10000000000000000;
  }
  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)
  {
    int it=n+1;
    while(te!=so)
    {
      if(te==it)
        exit(1);
      ap[t].pb(te);
      p[t][lu[te].F][lu[te].S]=1;
      it=te;
      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]=10000000000000000;
          dis[t][i][j]=10000000000000000;
        }
      }
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli test=1;
  for(;test>0;--test)
  {
    cin>>n>>m;
    lli d[201][m];
    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][int(al[f].size())-1]=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=10000000000000000;
          for(lli k=0;k<ap[0].size();++k)
          {
            for(lli l=int(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=10000000000000000;
          for(lli k=0;k<ap[1].size()-1;++k)
          {
            for(lli l=int(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][j]);
      }
    }
    if(ans>=10000000000000000)
      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:68: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:136:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(lli j=0;j<al[i].size();++j)
                   ~^~~~~~~~~~~~~
ho_t4.cpp:144:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(lli k=0;k<ap[0].size();++k)
                       ~^~~~~~~~~~~~~
ho_t4.cpp:161:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
           for(lli k=0;k<ap[1].size()-1;++k)
                       ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 2796 KB Output is correct
2 Correct 77 ms 2296 KB Output is correct
3 Correct 231 ms 2808 KB Output is correct
4 Correct 250 ms 2852 KB Output is correct
5 Correct 15 ms 1408 KB Output is correct
6 Correct 77 ms 2296 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 5 ms 1024 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 217 ms 3052 KB Output is correct
11 Correct 239 ms 3112 KB Output is correct
12 Incorrect 218 ms 3064 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 2808 KB Output is correct
2 Correct 80 ms 2296 KB Output is correct
3 Execution timed out 1090 ms 3448 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 2796 KB Output is correct
2 Correct 77 ms 2296 KB Output is correct
3 Correct 231 ms 2808 KB Output is correct
4 Correct 250 ms 2852 KB Output is correct
5 Correct 15 ms 1408 KB Output is correct
6 Correct 77 ms 2296 KB Output is correct
7 Correct 5 ms 1024 KB Output is correct
8 Correct 5 ms 1024 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 217 ms 3052 KB Output is correct
11 Correct 239 ms 3112 KB Output is correct
12 Incorrect 218 ms 3064 KB Output isn't correct
13 Halted 0 ms 0 KB -