oj.uz

Submission #1115170

# Submission time Handle Problem Language Result Execution time Memory
1115170 2024-11-20T08:10:03 Z staszic_ojuz Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 15944 KB 
#include <bits/stdc++.h>
using namespace std;
long long k[50000][4];
long long inf = (long long)1000000000*1000000000;
long long dis[4][200][2];
map<vector<long long>,int> kr;
vector<vector<vector<long long>>> gr[2];
priority_queue<vector<long long>> pq;
void dk(long long v,long long c,long long p,long long p2)
{
    for(int i = 0;i<gr[p2][v].size();i++)
    {
        if(v == 4)
        {
          //  cout<<v<<" "<<c<<" "<<i<<" "<<p<<" "<<p2<<" "<<dis[p][gr[p2][v][i][0]][0]<<" "<<gr[p2][v][i][1]<<"\n";
        }
        if(dis[p][gr[p2][v][i][0]][0] > c+gr[p2][v][i][1] ||(dis[p][gr[p2][v][i][0]][0] >= c+gr[p2][v][i][1] && k[dis[p][gr[p2][v][i][0]][1]][3] > gr[p2][v][i][2]))
        {
            pq.push({-1*(c+gr[p2][v][i][1]),gr[p2][v][i][0],p,p2});
            dis[p][gr[p2][v][i][0]][0] = gr[p2][v][i][1]+c;
            if(p2 == 0)
            {
                dis[p][gr[p2][v][i][0]][1] = kr[{v,gr[p2][v][i][0],gr[p2][v][i][1],gr[p2][v][i][2]}];
            }
            else
            {
                dis[p][gr[p2][v][i][0]][1] = kr[{gr[p2][v][i][0],v,gr[p2][v][i][1],gr[p2][v][i][2]}];
            }

        }
    }
}
priority_queue<vector<long long>> pq2;
long long dis2[200];
void dk2(long long c,long long v)
{
    for(int i = 0;i<gr[0][v].size();i++)
    {
        if(dis2[gr[0][v][i][0]] > c+gr[0][v][i][1])
        {
            pq2.push({-1*(c+gr[0][v][i][1]),gr[0][v][i][0]});
            dis2[gr[0][v][i][0]] = c+gr[0][v][i][1];
        }
    }
}
void del()
{
    for(int i = 0;i<200;i++)
    {
        dis2[i] = inf;
    }
}
int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    int n,m;
    cin>>n>>m;
    gr[0].resize(n);
    gr[1].resize(n);
    for(int i = 0;i<4;i++)
    {
        for(int j = 0;j<n;j++)
        {
            dis[i][j][0] = inf;
            dis[i][j][1] = -1;
        }
    }
    for(int i = 0;i<m;i++)
    {
        long long u,v,c,d;
        cin>>u>>v>>c>>d;
        u--;v--;
        kr[{u,v,c,d}] = i;
        gr[0][u].push_back({v,c,d});
        gr[1][v].push_back({u,c,d});
        k[i][0] = u;
        k[i][1] = v;
        k[i][2] = c;
        k[i][3] = d;
    }
    pq.push({0,0,0,0});
    pq.push({0,0,1,1});
    pq.push({0,n-1,2,0});
    pq.push({0,n-1,3,1});
    while(!pq.empty())
    {
        long long a,b,c,d;
        a = pq.top()[1];
        b = pq.top()[0]*-1;
        c = pq.top()[2];
        d = pq.top()[3];
        pq.pop();
        dk(a,b,c,d);

    }
    for(int i = 0;i<4;i++)
    {
        for(int j = 0;j<n;j++)
        {
         //   cout<<dis[i][j][1]<<" "<<i<<" "<<j<<"\n";
        }
    }
    set<long long> sps;
    for(int i = 0;i<2;i++)
    {
        for(int j = 1;j<n;j++)
        {
            if(dis[i][j][1] != -1)
            {
                sps.insert(dis[i][j][1]);
            }
            else
            {
      //          cout<<i<<" "<<j<<"\n";
            }
        }
/*5 5
1 2 0 4
2 3 0 4
5 3 0 4
5 3 0 2
3 1 0 9*/
    }
    for(int i = 2;i<4;i++)
    {
        for(int j = 0;j<n-1;j++)
        {
            if(dis[i][j][1] != -1)
            {
                sps.insert(dis[i][j][1]);
                //cout<<i<<" "<<j<<" "<<dis[i][j][1]<<" q2\n";

            }
            else if(i == 2 && j == 2)
            {
                //cout<<i<<" "<<j<<" "<<dis[i][j][1]<<" q\n";
            }
        }
    }
    //cout<<"\n";
    //cout<<dis[0][n-1][0]<<" "<<dis[2][0][0]<<"\n";
    long long ans = dis[0][n-1][0]+dis[2][0][0];
    dis[2][n-1][0] = 0;
    dis[3][n-1][0] = 0;
    dis[0][0][0] = 0;
    dis[1][0][0] = 0;
    for(int i = 0;i<m;i++)
    {
        if(sps.find(i) == sps.end())
        {
            ans = min(ans,k[i][3]+min(dis[0][n-1][0],dis[0][k[i][1]][0]+k[i][2]+dis[3][k[i][0]][0])+min(dis[2][0][0],dis[2][k[i][1]][0]+k[i][2]+dis[1][k[i][0]][0]));
        }
    }
    del();
    //cout<<sps.size()<<" "<<ans<<"\n";
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<gr[0][i].size();j++)
        {
            if(sps.find(kr[{i,gr[0][i][j][0],gr[0][i][j][1],gr[0][i][j][2]}]) != sps.end())
            {
                long long cu = gr[0][i][j][0];
                long long cans = gr[0][i][j][2];
    //            cout<<cans<<" "<<cu<<" "<<i<<" a\n";
                gr[0][i][j][0] = i;
                gr[0][cu].push_back({i,gr[0][i][j][1]});
                pq2.push({0,0});
                while(!pq2.empty())
                {
                    long long a = pq2.top()[0]*-1,b = pq2.top()[1];
                    pq2.pop();
                    dk2(a,b);
                }
                cans += dis2[n-1];
      //          cout<<dis2[n-1]<<" f\n";
        //        cout<<cans<<" b\n" ;
                del();
                pq2.push({0,n-1});
                while(!pq2.empty())
                {
                    long long a = pq2.top()[0]*-1,b = pq2.top()[1];
                    pq2.pop();
                    dk2(a,b);
                }
                cans+=dis2[0];
          //      cout<<cans<<" j\n";
                del();
                gr[0][i][j][0] = cu;
                gr[0][cu].pop_back();
                ans = min(ans,cans);
            }
        }
    }
    if(ans >= inf)
    {
        cout<<-1;
    }
    else
    {
        cout<<ans;
    }



}

Compilation message

ho_t4.cpp: In function 'void dk(long long int, long long int, long long int, long long int)':
ho_t4.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0;i<gr[p2][v].size();i++)
      |                   ~^~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'void dk2(long long int, long long int)':
ho_t4.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0;i<gr[0][v].size();i++)
      |                   ~^~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:160:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(int j = 0;j<gr[0][i].size();j++)
      |                       ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 34 ms 828 KB Output is correct
4 Correct 34 ms 828 KB Output is correct
5 Correct 5 ms 592 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 26 ms 592 KB Output is correct
11 Correct 33 ms 592 KB Output is correct
12 Correct 31 ms 592 KB Output is correct
13 Correct 9 ms 592 KB Output is correct
14 Correct 19 ms 828 KB Output is correct
15 Correct 18 ms 888 KB Output is correct
16 Correct 22 ms 820 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 592 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 201 ms 12084 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 291 ms 15176 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 123 ms 15944 KB Output is correct
9 Correct 136 ms 15944 KB Output is correct
10 Incorrect 214 ms 15172 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 34 ms 828 KB Output is correct
4 Correct 34 ms 828 KB Output is correct
5 Correct 5 ms 592 KB Output is correct
6 Correct 2 ms 564 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 26 ms 592 KB Output is correct
11 Correct 33 ms 592 KB Output is correct
12 Correct 31 ms 592 KB Output is correct
13 Correct 9 ms 592 KB Output is correct
14 Correct 19 ms 828 KB Output is correct
15 Correct 18 ms 888 KB Output is correct
16 Correct 22 ms 820 KB Output is correct
17 Execution timed out 1073 ms 15796 KB Time limit exceeded
18 Halted 0 ms 0 KB -