Submission #569837

#	Time	Username	Problem	Language	Result	Execution time	Memory
569837		Ronin13	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	468 ms	11568 KiB

ho_t4

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const ll linf = 1e18 + 1;
const int NMAX = 201;
vector <pll> vec[NMAX][NMAX];
map<pair<pii, pll>, int> used;

bool comp1(pll a, pll b){
    return a.f < b.f;
}

bool comp2(pll a, pll b){
    return a.f + a.s < b.f + b.s;
}

bool comp3(pll a, pll b){
    return 2 * a.f + a.s < 2 * b.f + b.s;
}

vector <pair<ll, pll> > g[NMAX][2];

ll d[NMAX][NMAX][4];

void dijk(int a, int b, int ind, int bb){
    d[a][b][ind] = 0;
    if(a == b) return;
    set <pll> q;
    q.insert({d[a][b][ind], a});
    while(!q.empty()){
        int v = q.begin()->s;
        q.erase(q.begin());
        for(auto x : g[v][bb]){
            int to = x.f;
            if(to == b) continue;
            ll len = x.s.f;
            if(d[to][b][ind] > d[v][b][ind] + len){
                q.erase({d[to][b][ind], to});
                d[to][b][ind] = d[v][b][ind] + len;
                q.insert({d[to][b][ind], to});
            }
        }
    }
}
int n;

ll get(int v, int ind){
    ll x = d[n][v][0];
    ll y = d[1][v][1];
    ll mn1, mn2;
    mn1 = d[v][v][3];
    mn2 = d[v][v][0];
    for(int i = 0; i < g[v][0].size(); i++){
        if(i == ind) continue;
        int xx = g[v][0][i].f;
        ll  len = g[v][0][i].s.f;
        mn1 = min(mn1, d[xx][v][3] + len);
    }
    for(int i = 0; i < g[v][1].size(); i++){
        int xx = g[v][1][i].f;
        ll len = g[v][1][i].s.f;
        mn2 = min(mn2, d[xx][v][0] + len);
    }
    if(ind != g[v][0].size()){
        int xx = g[v][0][ind].f;
        ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
        mn2 = min(mn2, d[xx][v][0] + len);
    }
    x = min(x, mn1 + mn2);
    mn1 = d[v][v][2];
    mn2 = d[v][v][1];
    for(int i = 0; i < g[v][0].size(); i++){
        if(i == ind) continue;
        int xx = g[v][0][i].f;
        ll len = g[v][0][i].s.f;
        mn1 = min(mn1, d[xx][v][2] + len);
    }
    for(int i = 0; i < g[v][1].size(); i++){
        int xx = g[v][1][i].f;
        ll len = g[v][1][i].s.f;
        mn2 = min(mn2, d[xx][v][1] + len);
    }
    if(ind != g[v][0].size()){
        int xx = g[v][0][ind].f;
        ll len = g[v][0][ind].s.f + g[v][0][ind].s.s;
        mn2 = min(mn2, d[xx][v][1] + len);
    }
    y = min(mn1 + mn2, y);
    return x + y;
}


int main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    int  m; cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        ll c, d; cin >> u >> v >> c >> d;
        used[{{u, v}, {c, d}}]++;
        vec[u][v].pb({c, d});
    }
    //cout << 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(vec[i][j].empty()) continue;
            sort(vec[i][j].begin(), vec[i][j].end(), comp1);
            int x = 0;
            while(x < vec[i][j].size() && !used[{{i, j}, vec[i][j][x]}]) x++;
            if(x != vec[i][j].size()){
            g[i][0].pb({j, vec[i][j][x]});
            used[{{i, j}, vec[i][j][x]}]--;}
            sort(vec[i][j].begin(), vec[i][j].end(), comp2);
            x = 0;
            while(x < vec[i][j].size() && !used[{{i, j}, vec[i][j][x]}]) x++;
            if(x != vec[i][j].size()){
            g[i][0].pb({j, vec[i][j][x]});
            used[{{i, j}, vec[i][j][x]}]--;}
            sort(vec[i][j].begin(), vec[i][j].end(), comp3);
            x = 0;
            while(x < vec[i][j].size() && !used[{{i, j}, vec[i][j][x]}]) x++;
            if(x != vec[i][j].size()){
            g[i][0].pb({j, vec[i][j][x]});
            used[{{i, j}, vec[i][j][x]}]--;}
        }
    }
   // cout << 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k  = 0; k < 4; k++){
                d[i][j][k] = linf;
            }

        }
    }
    for(int i = 1; i <= n; i++){
        for(auto to : g[i][0]){
            int x = to.f;
            pll v = to.s;
            g[x][1].pb({i, v});
        }
    }
    //cout << 1;
    for(int i = 1; i <= n; i++){
        dijk(1, i, 0, 0);
        dijk(n, i, 1, 0);
        dijk(1, i, 2, 1);
        dijk(n, i, 3, 1);
    }
    //cout << 1;
    ll ans = linf;
    for(int i = n; i >= 1; i--){
        for(int j = 0; j <= g[i][0].size(); j++){
            //cout << i << ' ' << g[i][0][j].f << ' ' << get(i, j) << "\n";
            ans = min(ans, get(i, j));
        }

    }
    if(ans == linf) cout << -1 << "\n";
    else cout << ans;
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'long long int get(int, int)':
ho_t4.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < g[v][0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < g[v][1].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:72:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     if(ind != g[v][0].size()){
      |        ~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i < g[v][0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i = 0; i < g[v][1].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
ho_t4.cpp:91:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     if(ind != g[v][0].size()){
      |        ~~~~^~~~~~~~~~~~~~~~~
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:116:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             while(x < vec[i][j].size() && !used[{{i, j}, vec[i][j][x]}]) x++;
      |                   ~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             if(x != vec[i][j].size()){
      |                ~~^~~~~~~~~~~~~~~~~~~
ho_t4.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             while(x < vec[i][j].size() && !used[{{i, j}, vec[i][j][x]}]) x++;
      |                   ~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             if(x != vec[i][j].size()){
      |                ~~^~~~~~~~~~~~~~~~~~~
ho_t4.cpp:128:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             while(x < vec[i][j].size() && !used[{{i, j}, vec[i][j][x]}]) x++;
      |                   ~~^~~~~~~~~~~~~~~~~~
ho_t4.cpp:129:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |             if(x != vec[i][j].size()){
      |                ~~^~~~~~~~~~~~~~~~~~~
ho_t4.cpp:160:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(int j = 0; j <= g[i][0].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63