Submission #1181143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181143		Szymon_Pilipczuk	Olympic Bus (JOI20_ho_t4)	C++20	Compilation error	0 ms	0 KiB

ho_t4

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int k[50000][4];
ll inf = 1e12;
ll dis[4][200];
vector<int> dis3[4][200];
map<vector<int>,int> kr;
vector<vector<vector<int>>> gr[2];
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
void dk(int v,int c,int p)
{
    for(vector<int> i : gr[p%2][v])
    {
        if(dis[p][i[0]] > c+i[1])
        {
            pq.push({c+i[1],i[0],p});
            dis[p][i[0]] = i[1]+c;
            if(p%2 == 0)
            {
                dis3[p][i[0]] = {v,i[0],i[1],i[2]};
            }
            else
            {
                dis3[p][i[0]] = {i[0],v,i[1],i[2]};
            }

        }
    }
}
ll dis2[200];
void dk2(int c,int v)
{
    for(vector<int> i : gr[0][v])
    {
        if(dis2[i[0]] > c+i[1])
        {
            pq.push({c+i[1],i[0]});
            dis2[i[0]] = c+i[1];
        }
    }
}
void del()
{
    for(int i = 0;i<n;i++)
    {
        dis2[i] = inf;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    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] = inf;
        }
    }
    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});
    pq.push({0,0,1});
    pq.push({0,n-1,2});
    pq.push({0,n-1,3});
    dis[0][0]= 0;
    dis[1][0] = 0;
    dis[2][n-1] = 0;
    dis[3][n-1] = 0;
    while(!pq.empty())
    {
        int a,b,c;
        a = pq.top()[1];
        b = pq.top()[0];
        c = pq.top()[2];
        pq.pop();
        if(dis[c][a] == b)
        {
            dk(a,b,c);
        }
    }
    unordered_set<int> sps;
    for(int i = 0;i<2;i++)
    {
        for(int j = 1;j<n;j++)
        {
            if(dis3[i][j].size() != 0)
            {
                sps.insert(kr[dis3[i][j]]);
            }
        }
    }
    for(int i = 2;i<4;i++)
    {
        for(int j = 0;j<n-1;j++)
        {
            if(dis3[i][j].size() != 0)
            {
                sps.insert(kr[dis3[i][j]]);
            }
        }
    }
    ll ans = dis[0][n-1]+dis[2][0];
    dis[2][n-1] = 0;
    dis[3][n-1] = 0;
    dis[0][0] = 0;
    dis[1][0] = 0;
    for(int i = 0;i<m;i++)
    {
        if(sps.find(i) == sps.end())
        {
            ans = min(ans,(ll)k[i][3]+min(dis[0][n-1],dis[0][k[i][1]]+k[i][2]+dis[3][k[i][0]])+min(dis[2][0],dis[2][k[i][1]]+k[i][2]+dis[1][k[i][0]]));
        }
    }
    del();
    for(int i = 0;i<n;i++)
    {
        for(int j : gr[0][i])
        {
            if(sps.find(kr[{i,j[0],j[1],j[2]}]) != sps.end())
            {

                int cu = j[0];
                ll cans = j[2];
                j[0] = i;
                gr[0][cu].push_back({i,j[1]});
                pq.push({0,0});
                dis2[0] = 0;
                while(!pq.empty())
                {
                    int a = pq.top()[0],b = pq.top()[1];
                    pq.pop();
                    if(dis2[b] == a)
                    {
                        dk2(a,b);
                    }
                }
                cans += dis2[n-1];
                del();
                pq.push({0,n-1});
                dis2[n-1] =0 ;
                while(!pq.empty())
                {
                    int a = pq.top()[0],b = pq.top()[1];
                    pq.pop();
                    if(dis2[b]== a)
                    {
                        dk2(a,b);
                    }

                }
                cans+=dis2[0];
                del();
                j[0] = cu;
                gr[0][cu].pop_back();
                ans = min(ans,cans);
            }
        }
    }
    if(ans >= inf)
    {
        cout<<-1<<"\n";
    }
    else
    {
        cout<<ans<<"\n";
    }
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:137:28: error: cannot convert 'std::vector<int>' to 'int' in initialization
  137 |         for(int j : gr[0][i])
      |                            ^
ho_t4.cpp:139:32: error: invalid types 'int[int]' for array subscript
  139 |             if(sps.find(kr[{i,j[0],j[1],j[2]}]) != sps.end())
      |                                ^
ho_t4.cpp:139:37: error: invalid types 'int[int]' for array subscript
  139 |             if(sps.find(kr[{i,j[0],j[1],j[2]}]) != sps.end())
      |                                     ^
ho_t4.cpp:139:42: error: invalid types 'int[int]' for array subscript
  139 |             if(sps.find(kr[{i,j[0],j[1],j[2]}]) != sps.end())
      |                                          ^
ho_t4.cpp:139:27: error: no match for 'operator[]' (operand types are 'std::map<std::vector<int>, int>' and '<brace-enclosed initializer list>')
  139 |             if(sps.find(kr[{i,j[0],j[1],j[2]}]) != sps.end())
      |                           ^
In file included from /usr/include/c++/11/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:81,
                 from ho_t4.cpp:2:
/usr/include/c++/11/bits/stl_map.h:492:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::vector<int>; _Tp = int; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::pair<const std::vector<int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::vector<int>]'
  492 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_map.h:492:34: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::vector<int>&'}
  492 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_map.h:512:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::vector<int>; _Tp = int; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::pair<const std::vector<int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::vector<int>]'
  512 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/11/bits/stl_map.h:512:29: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::map<std::vector<int>, int>::key_type&&' {aka 'std::vector<int>&&'}
  512 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
ho_t4.cpp:142:27: error: invalid types 'int[int]' for array subscript
  142 |                 int cu = j[0];
      |                           ^
ho_t4.cpp:143:28: error: invalid types 'int[int]' for array subscript
  143 |                 ll cans = j[2];
      |                            ^
ho_t4.cpp:144:18: error: invalid types 'int[int]' for array subscript
  144 |                 j[0] = i;
      |                  ^
ho_t4.cpp:145:41: error: invalid types 'int[int]' for array subscript
  145 |                 gr[0][cu].push_back({i,j[1]});
      |                                         ^
ho_t4.cpp:145:36: error: no matching function for call to 'std::vector<std::vector<int> >::push_back(<brace-enclosed initializer list>)'
  145 |                 gr[0][cu].push_back({i,j[1]});
      |                 ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from ho_t4.cpp:2:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::vector<int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; std::vector<_Tp, _Alloc>::value_type = std::vector<int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::vector<int> >::value_type&&' {aka 'std::vector<int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
ho_t4.cpp:173:18: error: invalid types 'int[int]' for array subscript
  173 |                 j[0] = cu;
      |                  ^