Submission #402729

#	Time	Username	Problem	Language	Result	Execution time	Memory
402729		Collypso	Swapping Cities (APIO20_swap)	C++17	0 / 100	2 ms	332 KiB

swap

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
//#define endl '\n'
//#define int ll

using namespace std;

vt<vt<pair<int, int>>> g;
vt<int> MP, weight, logTable;
vt<vt<int>> sparseTable;

void dfs(int v, int p = -1, int d = 0)
{
    MP[v] = d;
    for(auto x : g[v])
    {
        if (x.first == p) continue;
        weight[d] = x.second;
        dfs(x.first, v, d + 1);
    }
}

void init(int N, int M, vt<int> U, vt<int> V, vt<int> W)
{
    g.resize(N);
    vt<int> deg(N);
    for(int i = 0; i < M; i++)
    {
        g[U[i]].pb({V[i], W[i]});
        g[V[i]].pb({U[i], W[i]});
        deg[U[i]]++, deg[V[i]]++;
    }
    MP.resize(N), weight.resize(M);
    int root = 0;
    while(deg[root] != 1) root++;
    dfs(root);
    logTable.resize(N + 1);
    for(int i = 2; i <= N; i++)  logTable[i] = logTable[i / 2] + 1;
    sparseTable.resize(logTable[N] + 1);
    sparseTable[0] = weight;
    for(int i = 1, power = 2; i <= logTable[N]; i++, power *= 2)
    {
        sparseTable[i].resize(N - power);
        for(int j = 0; j < N - power + 1; j++)
        {
            sparseTable[i][j] = max(sparseTable[i - 1][j], sparseTable[i - 1][j + power / 2]);
        }
    }

    for(int i = 0; i < N; i++)
    {
        for(auto& x : g[i]) x.first = MP[x.first];
        if (sz(g[i]) == 1 && g[i][0].first == 1) g[i].pb({-1, INT_MAX});
        else if (sz(g[i]) == 1) g[i].pb({N, INT_MAX});
        sort(all(g[i]));
        //cout << g[i][0].first << " " << g[i][1].first << endl;
    }
}

int getMinimumFuelCapacity(int X, int Y)
{
    if (MP[Y] < MP[X]) swap(X, Y);
    int lg = logTable[MP[Y] - MP[X]];
    int l = sparseTable[lg][MP[X]];
    int r = sparseTable[lg][MP[Y] - (1 << lg)];
    int minFuel = max(l, r);
    //cout << X << " " << Y << " " << g[X][1].second << " " << g[Y][0].second << endl;
    minFuel = max(minFuel, min(g[X][0].second, g[Y][1].second));
    if (minFuel == INT_MAX) return -1;
    return minFuel;
}

/**
main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    freopen("input.txt", "r", stdin);
    int N, M;
    cin >> N >> M;
    vt<int> U(M), V(M), W(M);
    for(int i = 0; i < M; i++) cin >> U[i];
    for(int i = 0; i < M; i++) cin >> V[i];
    for(int i = 0; i < M; i++) cin >> W[i];
    init(N, M, U, V, W);
    cout << getMinimumFuelCapacity(2, 5) << endl;
}
/**/

Compilation message (stderr)

swap.cpp:94:1: warning: "/*" within comment [-Wcomment]
   94 | /**/
      |

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