Submission #1258527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258527		M_SH_O	Swapping Cities (APIO20_swap)	C++20	0 / 100	0 ms	324 KiB

swap

/*#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/
#include <bits/stdc++.h>
#include "swap.h"
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/

#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
//using namespace __gnu_pbds;

const ll INF = 1e18;
const int lg = 20;

mt19937 rng(time(0));
ll randll(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

vector<vpll> g;
ll n;

void init(int N, int m, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    g.resize(n+7);
    for (int i = 0; i < m; i ++) {
        g[U[i]].pb({V[i], W[i]});
        g[V[i]].pb({U[i], W[i]});
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    vvll d(2, vll(n+7, INF));
    d[0][X] = 0;
    set<pair<ll, pll>> s;
    for (int i = 1; i <= n; i ++) {
        s.insert({d[0][i], {0, i}});
        s.insert({d[1][i], {1, i}});
    }

    while (!s.empty()) {
        pair<ll, pll> p = *s.begin();
        s.erase(s.begin());

        for (auto i : g[p.se.se]) {
            if (i.fr == X) continue;
            if (p.fr + i.se < d[0][i.fr]) {
                s.erase({d[0][i.fr], {0, i.fr}});
                s.erase({d[1][i.fr], {1, i.fr}});
                d[1][i.fr] = d[0][i.fr];
                d[0][i.fr] = p.fr+i.se;
                s.insert({d[0][i.fr], {0, i.fr}});
                s.insert({d[1][i.fr], {1, i.fr}});
            }
            else if (p.fr + i.se < d[1][i.fr]) {
                s.erase({d[1][i.fr], {1, i.fr}});
                d[1][i.fr] = p.fr+i.se;
                s.insert({d[1][i.fr], {1, i.fr}});
            }
        }
    }
    /*for (int i = 1; i <= n; i ++) {
        cout << d[0][i] << ' ' << d[1][i] << endl;
    }*/
    if (d[1][Y] == INF) return -1;
    return d[1][Y];
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27