oj.uz

Submission #404111

# Submission time Handle Problem Language Result Execution time Memory
404111 2021-05-13T19:26:52 Z Collypso Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 21528 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<pair<int, int>> dsu;

int dsuValue(int x)
{
    if (dsu[x].F == x) return x;
    return dsu[x].F = dsuValue(dsu[x].F);
}

void dsuMerge(int x, int y)
{
    x = dsuValue(x), y = dsuValue(y);
    if (dsu[y].S < dsu[x].S) swap(x, y);
    dsu[x].F = y;
    dsu[y].S += dsu[x].S;
}

vt<vt<pair<int, int>>> g, mst;
vt<bool> marked, used;

void init(int N, int M, vt<int> U, vt<int> V, vt<int> W)
{
    g.resize(N), mst.resize(N), dsu.resize(N), marked.resize(N), used.resize(N);
    vt<pair<int, pair<int, int>>> edges;
    for(int i = 0; i < M; i++)
    {
        g[U[i]].pb({W[i], V[i]});
        g[V[i]].pb({W[i], U[i]});
        edges.pb({W[i], {U[i], V[i]}});
    }
    sort(all(edges));
    for(int i = 0; i < N; i++) sort(all(g[i])), dsu[i] = {i, 1};
    for(int i = 0; i < M; i++)
    {
        int u, v, w;
        u = edges[i].S.F, v = edges[i].S.S, w = edges[i].F;
        if (dsuValue(u) == dsuValue(v)) continue;
        mst[u].pb({v, w}), mst[v].pb({u, w});
        dsuMerge(u, v);
    }
}

bool completed;
vt<int> path, pathW;

void dfs1(int v, int to, int p = -1)
{
    if (v == to) completed = 1;
    if (completed) return;
    for(auto u : mst[v])
    {
        if (u.F == p) continue;
        path.pb(u.F), pathW.pb(u.S);
        dfs1(u.F, to, v);
        if (completed) return;
        path.pop_back(), pathW.pop_back();
    }
}

int maxFuel;

void dfs2(int v, int firstV, int firstU, int p = -1, int mx = 0)
{
    used[v] = 1;
    for(int i = 0; i < sz(g[v]); i++)
    {
        int u = g[v][i].S, w = g[v][i].F;
        if ((u == p) || (v == firstV && u == firstU)) continue;
        if (used[u])
        {
            maxFuel = min(maxFuel, max(mx, w));
            break;
        }
        mx = max(mx, w);
        if (sz(g[v]) - i >= 2)
        {
            if (g[v][i + 1].S == p || marked[g[v][i + 1].S])
            {
                if (sz(g[v]) - i >= 3) maxFuel = min(maxFuel, max(mx, g[v][i + 2].F));
            }
            else maxFuel = min(maxFuel, max(mx, g[v][i + 1].F));
        }
        dfs2(u, firstV, firstU, v, mx);
        break;
    }
}

int getMinimumFuelCapacity(int X, int Y)
{
    completed = 0;
    path.clear(), pathW.clear(), fill(all(marked), 0);
    // CLEAR (FILL MARKED WITH 0) EVERYTHING

    path.pb(X);
    dfs1(X, Y);
    for(int x : path) marked[x] = 1;
    maxFuel = INT_MAX;
    for(int i = 1; i < sz(path) - 1; i++)
    {
        for(auto v : g[i])
        {
            if (marked[v.S]) continue;
            maxFuel = min(maxFuel, v.F);
        }
    }

    fill(all(used), 0);
    used[Y] = 1;
    dfs2(X, X, path[1]);

    fill(all(used), 0);
    used[X] = 1;
    dfs2(Y, Y, path[sz(path) - 2]);

    for(int x : pathW) maxFuel = max(maxFuel, x);

    if (maxFuel == INT_MAX) return -1;
    return maxFuel;
}

/**
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:154:1: warning: "/*" within comment [-Wcomment]
  154 | /**/
      |

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 2059 ms 21528 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -