oj.uz

Submission #1115039

# Submission time Handle Problem Language Result Execution time Memory
1115039 2024-11-19T23:02:21 Z AdamGS Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 15036 KB 
#include <bits/stdc++.h>
using namespace std;
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)
{
    //cout<<v<<" v\n";
    for(int i = 0;i<gr[p2][v].size();i++)
    {
        if(dis[p][gr[p2][v][i][0]][0] > c+gr[p2][v][i][1])
        {
            pq.push({-1*(c+gr[p2][v][i][1]),gr[p2][v][i][0],p,p2});
    //        cout<<gr[p2][v][i][0]<<" "<<gr[p2][v].size()<<" gr\n";
            /* cos sie psuje if(gr[0][v][i][0] == 3&&p == 0)cout<<c+gr[0][v][i][1]<<" c\n";
            4 6
1 2 0 4
2 3 0 3
3 4 0 2
4 2 0 1
2 1 0 4
3 1 0 4*/
            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;
        }
    }
    long long k[m][4];
    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);

    }
    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]);
            }
        }
    }
    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<<dis[0][n-1][0]<<" "<<dis[2][0][0]<<"\n";
    long long ans = dis[0][n-1][0]+dis[2][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:42: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]
   42 |     for(int i = 0;i<gr[0][v].size();i++)
      |                   ~^~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:138: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]
  138 |         for(int j = 0;j<gr[0][i].size();j++)
      |                       ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 30 ms 592 KB Output is correct
4 Correct 33 ms 592 KB Output is correct
5 Correct 4 ms 808 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 2 ms 592 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 592 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 332 ms 11524 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 424 ms 14300 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 149 ms 15036 KB Output is correct
9 Correct 163 ms 14872 KB Output is correct
10 Correct 275 ms 14408 KB Output is correct
11 Correct 255 ms 14664 KB Output is correct
12 Correct 299 ms 14408 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Incorrect 1 ms 336 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 30 ms 592 KB Output is correct
4 Correct 33 ms 592 KB Output is correct
5 Correct 4 ms 808 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Incorrect 2 ms 592 KB Output isn't correct
10 Halted 0 ms 0 KB -