oj.uz

Submission #245475

# Submission time Handle Problem Language Result Execution time Memory
245475 2020-07-06T14:00:21 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[1].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;
    exit(0);
  }
  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[1].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 259 ms 2808 KB Output is correct
2 Correct 87 ms 2236 KB Output is correct
3 Correct 225 ms 2808 KB Output is correct
4 Correct 252 ms 2760 KB Output is correct
5 Correct 16 ms 1408 KB Output is correct
6 Correct 108 ms 2272 KB Output is correct
7 Correct 6 ms 1024 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 218 ms 3064 KB Output is correct
11 Correct 224 ms 3064 KB Output is correct
12 Incorrect 226 ms 3128 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 1090 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 233 ms 2868 KB Output is correct
2 Correct 80 ms 2296 KB Output is correct
3 Execution timed out 1096 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 259 ms 2808 KB Output is correct
2 Correct 87 ms 2236 KB Output is correct
3 Correct 225 ms 2808 KB Output is correct
4 Correct 252 ms 2760 KB Output is correct
5 Correct 16 ms 1408 KB Output is correct
6 Correct 108 ms 2272 KB Output is correct
7 Correct 6 ms 1024 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Correct 6 ms 1152 KB Output is correct
10 Correct 218 ms 3064 KB Output is correct
11 Correct 224 ms 3064 KB Output is correct
12 Incorrect 226 ms 3128 KB Output isn't correct
13 Halted 0 ms 0 KB -