oj.uz

Submission #319833

# Submission time Handle Problem Language Result Execution time Memory
319833 2020-11-06T14:21:11 Z arujbansal Swapping Cities (APIO20_swap) C++17
7 / 100
 285 ms 18380 KB 
#include "swap.h"
#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

const int MAXN = 1e5 + 20, MOD = 1e9 + 7, INF = 1e9;

struct Edge {
    int u, v, w;

    bool operator<(const Edge &other) {
        return w < other.w;
    }
};

struct DSU {
    int n;
    vi par, s, deg, mxDeg, timeValid;
    vii root[MAXN];

    void init(int n) {
        this->n = n;
        par.resize(n);
        iota(all(par), 0);
        s.assign(n, 1);
        deg.assign(n, 0);
        mxDeg.assign(n, 0);
        timeValid.assign(n, INF);

        for (int i = 0; i < n; i++)
            root[i].eb(0, i);
    }

    int get(int x) {
        if (par[x] == x) return x;
        return get(par[x]);
    }

    void unite(int u, int v, int time) {
        deg[u]++;
        deg[v]++;

        int x = get(u);
        int y = get(v);

        if (deg[u] >= 3) timeValid[x] = min(timeValid[x], time);
        if (deg[v] >= 3) timeValid[y] = min(timeValid[y], time);

        if (x == y) {
            timeValid[x] = min(timeValid[x], time);
            return;
        }

        if (s[x] > s[y]) {
            swap(x, y);
            swap(u, v);
        }

        par[x] = y;
        s[y] += s[x];
        timeValid[y] = min(timeValid[y], timeValid[x]);

        root[u].eb(time, y);
    }

    bool query(int u, int v, int time) {
        time++;

        auto x = upper_bound(all(root[u]), ii(time, INF));
        auto y = upper_bound(all(root[v]), ii(time, INF));
        x--, y--;

        ii rootU = *x;
        ii rootV = *y;

        if (rootU.second == rootV.second)
            return timeValid[rootU.second] <= time;

        return false;
    }
};

DSU graph;
vector<Edge> edges;
int n, m;

void init(int N, int M, vi U, vi V, vi W) {
    n = N;
    m = M;

    edges.resize(M);

    for (int i = 0; i < M; i++) {
        edges[i].u = U[i];
        edges[i].v = V[i];
        edges[i].w = W[i];
    }

    sort(all(edges));

    graph.init(N);

    for (int i = 0; i < M; i++)
        graph.unite(edges[i].u, edges[i].v, i + 1);
}

int getMinimumFuelCapacity(int X, int Y) {
    int lo = 0, hi = m - 1;
    int ans = INF;

    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (graph.query(X, Y, mid)) {
            ans = min(ans, edges[mid].w);
            hi = mid - 1;
        } else lo = mid + 1;
    }

    return ans < INF ? ans : -1;
}

//signed main() {
//    FAST_IO;
//#ifdef arujbansal_local
//    setIO("input.txt", "output.txt");
//#endif
//
//    int a, b;
//    cin >> a >> b;
//    int u[b], v[b], wt[b];
//
//    for (int i = 0; i < b; i++)
//        cin >> u[i] >> v[i] >> wt[i];
//
//    init(a, b, u, v, wt);
//
//    int q;
//    cin >> q;
//    while (q--) {
//        int x, y;
//        cin >> x >> y;
//        cout << getMinimumFuelCapacity(x, y) << "\n";
//    }
//
////    for (const auto &[time, root] : graph.root[4])
////        cout << time << " " << root << "\n";
//}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 100 ms 11824 KB Output is correct
10 Correct 84 ms 13796 KB Output is correct
11 Correct 82 ms 13668 KB Output is correct
12 Correct 88 ms 14304 KB Output is correct
13 Correct 86 ms 13412 KB Output is correct
14 Correct 78 ms 12132 KB Output is correct
15 Correct 228 ms 18112 KB Output is correct
16 Correct 224 ms 17996 KB Output is correct
17 Correct 217 ms 18380 KB Output is correct
18 Correct 215 ms 17612 KB Output is correct
19 Incorrect 100 ms 8548 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 285 ms 17672 KB Output is correct
4 Correct 233 ms 18124 KB Output is correct
5 Correct 243 ms 18172 KB Output is correct
6 Correct 229 ms 17868 KB Output is correct
7 Correct 253 ms 18192 KB Output is correct
8 Correct 244 ms 17684 KB Output is correct
9 Correct 249 ms 18148 KB Output is correct
10 Correct 245 ms 17696 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Incorrect 3 ms 2796 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 100 ms 11824 KB Output is correct
11 Correct 84 ms 13796 KB Output is correct
12 Correct 82 ms 13668 KB Output is correct
13 Correct 88 ms 14304 KB Output is correct
14 Correct 86 ms 13412 KB Output is correct
15 Incorrect 3 ms 2796 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 100 ms 11824 KB Output is correct
10 Correct 84 ms 13796 KB Output is correct
11 Correct 82 ms 13668 KB Output is correct
12 Correct 88 ms 14304 KB Output is correct
13 Correct 86 ms 13412 KB Output is correct
14 Correct 78 ms 12132 KB Output is correct
15 Correct 228 ms 18112 KB Output is correct
16 Correct 224 ms 17996 KB Output is correct
17 Correct 217 ms 18380 KB Output is correct
18 Correct 215 ms 17612 KB Output is correct
19 Correct 285 ms 17672 KB Output is correct
20 Correct 233 ms 18124 KB Output is correct
21 Correct 243 ms 18172 KB Output is correct
22 Correct 229 ms 17868 KB Output is correct
23 Correct 253 ms 18192 KB Output is correct
24 Correct 244 ms 17684 KB Output is correct
25 Correct 249 ms 18148 KB Output is correct
26 Correct 245 ms 17696 KB Output is correct
27 Incorrect 3 ms 2796 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 100 ms 11824 KB Output is correct
11 Correct 84 ms 13796 KB Output is correct
12 Correct 82 ms 13668 KB Output is correct
13 Correct 88 ms 14304 KB Output is correct
14 Correct 86 ms 13412 KB Output is correct
15 Correct 78 ms 12132 KB Output is correct
16 Correct 228 ms 18112 KB Output is correct
17 Correct 224 ms 17996 KB Output is correct
18 Correct 217 ms 18380 KB Output is correct
19 Correct 215 ms 17612 KB Output is correct
20 Correct 285 ms 17672 KB Output is correct
21 Correct 233 ms 18124 KB Output is correct
22 Correct 243 ms 18172 KB Output is correct
23 Correct 229 ms 17868 KB Output is correct
24 Correct 253 ms 18192 KB Output is correct
25 Correct 244 ms 17684 KB Output is correct
26 Correct 249 ms 18148 KB Output is correct
27 Correct 245 ms 17696 KB Output is correct
28 Incorrect 3 ms 2796 KB Output isn't correct
29 Halted 0 ms 0 KB -