oj.uz

Submission #406993

# Submission time Handle Problem Language Result Execution time Memory
406993 2021-05-18T09:43:44 Z Collypso Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 524292 KB 
#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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 160 ms 29244 KB Output is correct
10 Correct 189 ms 36644 KB Output is correct
11 Correct 181 ms 35556 KB Output is correct
12 Correct 203 ms 37820 KB Output is correct
13 Correct 211 ms 39216 KB Output is correct
14 Correct 146 ms 28612 KB Output is correct
15 Correct 258 ms 38896 KB Output is correct
16 Correct 244 ms 36676 KB Output is correct
17 Correct 273 ms 41484 KB Output is correct
18 Correct 261 ms 40436 KB Output is correct
19 Execution timed out 2075 ms 253544 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 265 ms 35604 KB Output is correct
4 Correct 308 ms 37212 KB Output is correct
5 Correct 275 ms 36276 KB Output is correct
6 Correct 264 ms 37140 KB Output is correct
7 Correct 287 ms 36784 KB Output is correct
8 Correct 300 ms 35004 KB Output is correct
9 Correct 310 ms 36124 KB Output is correct
10 Correct 266 ms 34676 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Runtime error 519 ms 524292 KB Execution killed with signal 9

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 519 ms 524292 KB Execution killed with signal 9

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 160 ms 29244 KB Output is correct
10 Correct 189 ms 36644 KB Output is correct
11 Correct 181 ms 35556 KB Output is correct
12 Correct 203 ms 37820 KB Output is correct
13 Correct 211 ms 39216 KB Output is correct
14 Correct 146 ms 28612 KB Output is correct
15 Correct 258 ms 38896 KB Output is correct
16 Correct 244 ms 36676 KB Output is correct
17 Correct 273 ms 41484 KB Output is correct
18 Correct 261 ms 40436 KB Output is correct
19 Correct 265 ms 35604 KB Output is correct
20 Correct 308 ms 37212 KB Output is correct
21 Correct 275 ms 36276 KB Output is correct
22 Correct 264 ms 37140 KB Output is correct
23 Correct 287 ms 36784 KB Output is correct
24 Correct 300 ms 35004 KB Output is correct
25 Correct 310 ms 36124 KB Output is correct
26 Correct 266 ms 34676 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Incorrect 2 ms 460 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 519 ms 524292 KB Execution killed with signal 9