oj.uz

Submission #319849

# Submission time Handle Problem Language Result Execution time Memory
319849 2020-11-06T14:54:11 Z arujbansal Swapping Cities (APIO20_swap) C++17
13 / 100
 573 ms 33788 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];
    vi g[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) {
        return par[x];
    }

    void mark(int x, int newPar, int time) {
        if (par[x] == newPar) return;

        par[x] = newPar;
        root[x].eb(time, newPar);
        timeValid[newPar] = min(timeValid[newPar], timeValid[x]);

        for (const auto &v : g[x]) mark(v, newPar, time);
    }

    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;
        }

        g[u].pb(v);
        g[v].pb(u);

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

        mark(par[x], y, time);
        s[y] += s[x];
        timeValid[y] = min(timeValid[y], timeValid[x]);
        root[x].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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 5 ms 5484 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 4 ms 5228 KB Output is correct
9 Correct 252 ms 24164 KB Output is correct
10 Correct 319 ms 27512 KB Output is correct
11 Correct 317 ms 27108 KB Output is correct
12 Correct 344 ms 28520 KB Output is correct
13 Correct 132 ms 22760 KB Output is correct
14 Correct 271 ms 24036 KB Output is correct
15 Correct 542 ms 31984 KB Output is correct
16 Correct 525 ms 31208 KB Output is correct
17 Correct 573 ms 32716 KB Output is correct
18 Correct 313 ms 26496 KB Output is correct
19 Correct 160 ms 13668 KB Output is correct
20 Correct 517 ms 32300 KB Output is correct
21 Correct 517 ms 32292 KB Output is correct
22 Correct 555 ms 33788 KB Output is correct
23 Correct 291 ms 27468 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 296 ms 24324 KB Output is correct
4 Correct 300 ms 24872 KB Output is correct
5 Correct 300 ms 24820 KB Output is correct
6 Correct 293 ms 24648 KB Output is correct
7 Correct 313 ms 25024 KB Output is correct
8 Correct 301 ms 24204 KB Output is correct
9 Correct 286 ms 24540 KB Output is correct
10 Correct 303 ms 24088 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 5 ms 5484 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Correct 5 ms 5228 KB Output is correct
11 Correct 5 ms 5228 KB Output is correct
12 Correct 5 ms 5228 KB Output is correct
13 Correct 5 ms 5356 KB Output is correct
14 Correct 5 ms 5228 KB Output is correct
15 Correct 5 ms 5228 KB Output is correct
16 Correct 6 ms 5228 KB Output is correct
17 Correct 6 ms 5228 KB Output is correct
18 Correct 5 ms 5228 KB Output is correct
19 Correct 5 ms 5100 KB Output is correct
20 Correct 6 ms 5228 KB Output is correct
21 Correct 5 ms 5228 KB Output is correct
22 Correct 6 ms 5100 KB Output is correct
23 Correct 5 ms 5228 KB Output is correct
24 Incorrect 5 ms 5356 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 5 ms 5484 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Correct 252 ms 24164 KB Output is correct
11 Correct 319 ms 27512 KB Output is correct
12 Correct 317 ms 27108 KB Output is correct
13 Correct 344 ms 28520 KB Output is correct
14 Correct 132 ms 22760 KB Output is correct
15 Correct 5 ms 5228 KB Output is correct
16 Correct 5 ms 5228 KB Output is correct
17 Correct 5 ms 5228 KB Output is correct
18 Correct 5 ms 5356 KB Output is correct
19 Correct 5 ms 5228 KB Output is correct
20 Correct 5 ms 5228 KB Output is correct
21 Correct 6 ms 5228 KB Output is correct
22 Correct 6 ms 5228 KB Output is correct
23 Correct 5 ms 5228 KB Output is correct
24 Correct 20 ms 7788 KB Output is correct
25 Correct 327 ms 27876 KB Output is correct
26 Correct 323 ms 27620 KB Output is correct
27 Correct 320 ms 26716 KB Output is correct
28 Correct 287 ms 25444 KB Output is correct
29 Correct 284 ms 25060 KB Output is correct
30 Correct 234 ms 23272 KB Output is correct
31 Incorrect 353 ms 29284 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 5 ms 5484 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 4 ms 5228 KB Output is correct
9 Correct 252 ms 24164 KB Output is correct
10 Correct 319 ms 27512 KB Output is correct
11 Correct 317 ms 27108 KB Output is correct
12 Correct 344 ms 28520 KB Output is correct
13 Correct 132 ms 22760 KB Output is correct
14 Correct 271 ms 24036 KB Output is correct
15 Correct 542 ms 31984 KB Output is correct
16 Correct 525 ms 31208 KB Output is correct
17 Correct 573 ms 32716 KB Output is correct
18 Correct 313 ms 26496 KB Output is correct
19 Correct 296 ms 24324 KB Output is correct
20 Correct 300 ms 24872 KB Output is correct
21 Correct 300 ms 24820 KB Output is correct
22 Correct 293 ms 24648 KB Output is correct
23 Correct 313 ms 25024 KB Output is correct
24 Correct 301 ms 24204 KB Output is correct
25 Correct 286 ms 24540 KB Output is correct
26 Correct 303 ms 24088 KB Output is correct
27 Correct 5 ms 5228 KB Output is correct
28 Correct 5 ms 5228 KB Output is correct
29 Correct 5 ms 5228 KB Output is correct
30 Correct 5 ms 5356 KB Output is correct
31 Correct 5 ms 5228 KB Output is correct
32 Correct 5 ms 5228 KB Output is correct
33 Correct 6 ms 5228 KB Output is correct
34 Correct 6 ms 5228 KB Output is correct
35 Correct 5 ms 5228 KB Output is correct
36 Correct 20 ms 7788 KB Output is correct
37 Correct 327 ms 27876 KB Output is correct
38 Correct 323 ms 27620 KB Output is correct
39 Correct 320 ms 26716 KB Output is correct
40 Correct 287 ms 25444 KB Output is correct
41 Correct 284 ms 25060 KB Output is correct
42 Correct 234 ms 23272 KB Output is correct
43 Incorrect 353 ms 29284 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 5 ms 5484 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Correct 252 ms 24164 KB Output is correct
11 Correct 319 ms 27512 KB Output is correct
12 Correct 317 ms 27108 KB Output is correct
13 Correct 344 ms 28520 KB Output is correct
14 Correct 132 ms 22760 KB Output is correct
15 Correct 271 ms 24036 KB Output is correct
16 Correct 542 ms 31984 KB Output is correct
17 Correct 525 ms 31208 KB Output is correct
18 Correct 573 ms 32716 KB Output is correct
19 Correct 313 ms 26496 KB Output is correct
20 Correct 296 ms 24324 KB Output is correct
21 Correct 300 ms 24872 KB Output is correct
22 Correct 300 ms 24820 KB Output is correct
23 Correct 293 ms 24648 KB Output is correct
24 Correct 313 ms 25024 KB Output is correct
25 Correct 301 ms 24204 KB Output is correct
26 Correct 286 ms 24540 KB Output is correct
27 Correct 303 ms 24088 KB Output is correct
28 Correct 5 ms 5228 KB Output is correct
29 Correct 5 ms 5228 KB Output is correct
30 Correct 5 ms 5228 KB Output is correct
31 Correct 5 ms 5356 KB Output is correct
32 Correct 5 ms 5228 KB Output is correct
33 Correct 5 ms 5228 KB Output is correct
34 Correct 6 ms 5228 KB Output is correct
35 Correct 6 ms 5228 KB Output is correct
36 Correct 5 ms 5228 KB Output is correct
37 Correct 20 ms 7788 KB Output is correct
38 Correct 327 ms 27876 KB Output is correct
39 Correct 323 ms 27620 KB Output is correct
40 Correct 320 ms 26716 KB Output is correct
41 Correct 287 ms 25444 KB Output is correct
42 Correct 284 ms 25060 KB Output is correct
43 Correct 234 ms 23272 KB Output is correct
44 Incorrect 353 ms 29284 KB Output isn't correct
45 Halted 0 ms 0 KB -