Submission #406993

#	Time	Username	Problem	Language	Result	Execution time	Memory
406993		Collypso	Swapping Cities (APIO20_swap)	C++17	7 / 100	2075 ms	524292 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) (int) (x).size()
#define F first
#define S second
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
//#define endl '\n'
//#define int ll

using namespace std;

vt<vt<pair<int, int>>> g;
vt<vt<int>> parent, parentMax;
vt<int> timeEnter, timeExit;
int timer, logTmp;

void dfsLCA(int v, int p, int w = 0)
{
    timeEnter[v] = ++timer;
    parent[v][0] = p, parentMax[v][0] = w;
    for(int i = 1; i <= logTmp; i++)
    {
        parent[v][i] = parent[parent[v][i - 1]][i - 1];
        parentMax[v][i] = max(parentMax[v][i - 1], parentMax[parent[v][i - 1]][i - 1]);
    }
    for(auto to : g[v])
        if (to.F != p) dfsLCA(to.F, v, to.S);
    timeExit[v] = ++timer;
}

bool isAncestor(int v1, int v2)
{
    return timeEnter[v1] <= timeEnter[v2] && timeExit[v1] >= timeExit[v2];
}

int maxLCA(int v1, int v2)
{
    if (isAncestor(v1, v2)) swap(v1, v2);
    int val = 0;
    for(int i = logTmp; i >= 0; i--)
        if (!isAncestor(parent[v1][i], v2))
            val = max(val, parentMax[v1][i]), v1 = parent[v1][i];
    if (!isAncestor(v1, v2)) val = max(val, parentMax[v1][0]), v1 = parent[v1][0];
    for(int i = logTmp; i >= 0; i--)
        if (!isAncestor(parent[v2][i], v1))
            val = max(val, parentMax[v2][i]), v2 = parent[v2][i];
    if (!isAncestor(v2, v1)) val = max(val, parentMax[v2][0]), v2 = parent[v2][0];
    return val;
}

vt<int> dp;

void dfsDP1(int v, int p = -1)
{
    dp[v] = INT_MAX;
    if (sz(g[v]) >= 3) dp[v] = g[v][2].S;
    for(auto to : g[v])
    {
        if (to.F != p) dfsDP1(to.F, v);
        dp[v] = min(dp[v], max(to.S, dp[to.F]));
    }
}

void dfsDP2(int v, int p = -1)
{
    for(auto to : g[v])
    {
        if (to.F == p) continue;
        dp[to.F] = min(dp[to.F], max(to.S, dp[v]));
        dfsDP2(to.F, v);
    }
}

void init(int N, int M, vt<int> U, vt<int> V, vt<int> W)
{
    g.resize(N);
    for(int i = 0; i < M; i++) g[U[i]].pb({V[i], W[i]}), g[V[i]].pb({U[i], W[i]});
    logTmp = ceil(log2(N)) + 1;
    dp.resize(N), timeEnter.resize(N), timeExit.resize(N);
    parent.resize(N, vt<int>(logTmp + 1)), parentMax.resize(N, vt<int>(logTmp + 1));
    for(int i = 0; i < N; i++) sort(all(g[i]), [](auto& a, auto& b){return a.S < b.S;});
    dfsLCA(0, 0), dfsDP1(0);
}

int getMinimumFuelCapacity(int X, int Y)
{
    if (dp[X] == INT_MAX && dp[Y] == INT_MAX) return -1;
    return max(maxLCA(X, Y), min(dp[X], dp[Y]));
}

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

Compilation message (stderr)

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

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