oj.uz

Submission #1114958

# Submission time Handle Problem Language Result Execution time Memory
1114958 2024-11-19T20:48:17 Z AdamGS Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 15040 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)
{
    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});
            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 v,long long c)
{
    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;
        }
    }
    int k[m][4];
    for(int i = 0;i<m;i++)
    {
        int 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<int> sps;
    vector<int> sp;
    for(int i = 0;i<2;i++)
    {
        for(int j = 1;j<n;j++)
        {
            if(dis[i][j][1] != -1)
            {
                sp.push_back(dis[i][j][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)
            {
                sp.push_back(dis[i][j][1]);
                sps.insert(dis[i][j][1]);
            }
        }
    }
    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();
    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())
            {
                int 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()[1],b = pq2.top()[0]*-1;
                    pq2.pop();
                    dk2(a,b);
                }
                cans += dis2[n-1];
                del();
                pq2.push({0,n-1});
                while(!pq2.empty())
                {
                    long long a = pq2.top()[1],b = pq2.top()[0]*-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:10: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]
   10 |     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:32: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]
   32 |     for(int i = 0;i<gr[0][v].size();i++)
      |                   ~^~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:128: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]
  128 |         for(int j = 0;j<gr[0][i].size();j++)
      |                       ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 37 ms 592 KB Output is correct
4 Correct 35 ms 848 KB Output is correct
5 Correct 5 ms 592 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 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 1062 ms 14920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 592 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 340 ms 11644 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 404 ms 14236 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 162 ms 15024 KB Output is correct
9 Correct 163 ms 15040 KB Output is correct
10 Correct 267 ms 14408 KB Output is correct
11 Correct 275 ms 14920 KB Output is correct
12 Correct 231 ms 14664 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 592 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 20 ms 592 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 37 ms 592 KB Output is correct
4 Correct 35 ms 848 KB Output is correct
5 Correct 5 ms 592 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 Incorrect 2 ms 592 KB Output isn't correct
10 Halted 0 ms 0 KB -