oj.uz

Submission #1115571

# Submission time Handle Problem Language Result Execution time Memory
1115571 2024-11-20T16:06:21 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(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);

    }
    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]);
            }
        }
    }
    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();
    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];
                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];
                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];
                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:33: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]
   33 |     for(int i = 0;i<gr[0][v].size();i++)
      |                   ~^~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:130: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]
  130 |         for(int j = 0;j<gr[0][i].size();j++)
      |                       ~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 836 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 32 ms 848 KB Output is correct
4 Correct 33 ms 848 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 1 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 Correct 2 ms 728 KB Output is correct
10 Correct 25 ms 744 KB Output is correct
11 Correct 40 ms 760 KB Output is correct
12 Correct 32 ms 848 KB Output is correct
13 Correct 8 ms 592 KB Output is correct
14 Correct 18 ms 592 KB Output is correct
15 Correct 17 ms 840 KB Output is correct
16 Correct 18 ms 1016 KB Output is correct

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 592 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 179 ms 12128 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 223 ms 15180 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 112 ms 15904 KB Output is correct
9 Correct 127 ms 15944 KB Output is correct
10 Incorrect 190 ms 15184 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 836 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 32 ms 848 KB Output is correct
4 Correct 33 ms 848 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 1 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 Correct 2 ms 728 KB Output is correct
10 Correct 25 ms 744 KB Output is correct
11 Correct 40 ms 760 KB Output is correct
12 Correct 32 ms 848 KB Output is correct
13 Correct 8 ms 592 KB Output is correct
14 Correct 18 ms 592 KB Output is correct
15 Correct 17 ms 840 KB Output is correct
16 Correct 18 ms 1016 KB Output is correct
17 Execution timed out 1066 ms 15688 KB Time limit exceeded
18 Halted 0 ms 0 KB -