oj.uz

답안 #319784

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319784 2020-11-06T12:36:43 Z arujbansal 자매 도시 (APIO20_swap) C++17
7 / 100
 253 ms 14456 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 par[x] = 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(MAXN);

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7788 KB Output is correct
2 Correct 11 ms 7788 KB Output is correct
3 Correct 8 ms 7788 KB Output is correct
4 Correct 8 ms 7788 KB Output is correct
5 Correct 11 ms 7788 KB Output is correct
6 Correct 9 ms 7788 KB Output is correct
7 Correct 9 ms 7788 KB Output is correct
8 Correct 9 ms 7788 KB Output is correct
9 Correct 63 ms 11236 KB Output is correct
10 Correct 76 ms 12004 KB Output is correct
11 Correct 81 ms 11876 KB Output is correct
12 Correct 102 ms 12132 KB Output is correct
13 Correct 81 ms 11236 KB Output is correct
14 Correct 74 ms 11364 KB Output is correct
15 Correct 221 ms 13808 KB Output is correct
16 Correct 213 ms 13848 KB Output is correct
17 Correct 222 ms 14028 KB Output is correct
18 Correct 209 ms 13132 KB Output is correct
19 Incorrect 106 ms 10852 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7788 KB Output is correct
2 Correct 11 ms 7788 KB Output is correct
3 Correct 240 ms 14108 KB Output is correct
4 Correct 253 ms 14156 KB Output is correct
5 Correct 252 ms 14456 KB Output is correct
6 Correct 244 ms 14028 KB Output is correct
7 Correct 248 ms 14432 KB Output is correct
8 Correct 251 ms 14228 KB Output is correct
9 Correct 235 ms 14168 KB Output is correct
10 Correct 242 ms 14240 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7788 KB Output is correct
2 Correct 8 ms 7788 KB Output is correct
3 Correct 11 ms 7788 KB Output is correct
4 Correct 8 ms 7788 KB Output is correct
5 Correct 8 ms 7788 KB Output is correct
6 Correct 11 ms 7788 KB Output is correct
7 Correct 9 ms 7788 KB Output is correct
8 Correct 9 ms 7788 KB Output is correct
9 Correct 9 ms 7788 KB Output is correct
10 Incorrect 9 ms 7788 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7788 KB Output is correct
2 Correct 8 ms 7788 KB Output is correct
3 Correct 11 ms 7788 KB Output is correct
4 Correct 8 ms 7788 KB Output is correct
5 Correct 8 ms 7788 KB Output is correct
6 Correct 11 ms 7788 KB Output is correct
7 Correct 9 ms 7788 KB Output is correct
8 Correct 9 ms 7788 KB Output is correct
9 Correct 9 ms 7788 KB Output is correct
10 Correct 63 ms 11236 KB Output is correct
11 Correct 76 ms 12004 KB Output is correct
12 Correct 81 ms 11876 KB Output is correct
13 Correct 102 ms 12132 KB Output is correct
14 Correct 81 ms 11236 KB Output is correct
15 Incorrect 9 ms 7788 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7788 KB Output is correct
2 Correct 11 ms 7788 KB Output is correct
3 Correct 8 ms 7788 KB Output is correct
4 Correct 8 ms 7788 KB Output is correct
5 Correct 11 ms 7788 KB Output is correct
6 Correct 9 ms 7788 KB Output is correct
7 Correct 9 ms 7788 KB Output is correct
8 Correct 9 ms 7788 KB Output is correct
9 Correct 63 ms 11236 KB Output is correct
10 Correct 76 ms 12004 KB Output is correct
11 Correct 81 ms 11876 KB Output is correct
12 Correct 102 ms 12132 KB Output is correct
13 Correct 81 ms 11236 KB Output is correct
14 Correct 74 ms 11364 KB Output is correct
15 Correct 221 ms 13808 KB Output is correct
16 Correct 213 ms 13848 KB Output is correct
17 Correct 222 ms 14028 KB Output is correct
18 Correct 209 ms 13132 KB Output is correct
19 Correct 240 ms 14108 KB Output is correct
20 Correct 253 ms 14156 KB Output is correct
21 Correct 252 ms 14456 KB Output is correct
22 Correct 244 ms 14028 KB Output is correct
23 Correct 248 ms 14432 KB Output is correct
24 Correct 251 ms 14228 KB Output is correct
25 Correct 235 ms 14168 KB Output is correct
26 Correct 242 ms 14240 KB Output is correct
27 Incorrect 9 ms 7788 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7788 KB Output is correct
2 Correct 8 ms 7788 KB Output is correct
3 Correct 11 ms 7788 KB Output is correct
4 Correct 8 ms 7788 KB Output is correct
5 Correct 8 ms 7788 KB Output is correct
6 Correct 11 ms 7788 KB Output is correct
7 Correct 9 ms 7788 KB Output is correct
8 Correct 9 ms 7788 KB Output is correct
9 Correct 9 ms 7788 KB Output is correct
10 Correct 63 ms 11236 KB Output is correct
11 Correct 76 ms 12004 KB Output is correct
12 Correct 81 ms 11876 KB Output is correct
13 Correct 102 ms 12132 KB Output is correct
14 Correct 81 ms 11236 KB Output is correct
15 Correct 74 ms 11364 KB Output is correct
16 Correct 221 ms 13808 KB Output is correct
17 Correct 213 ms 13848 KB Output is correct
18 Correct 222 ms 14028 KB Output is correct
19 Correct 209 ms 13132 KB Output is correct
20 Correct 240 ms 14108 KB Output is correct
21 Correct 253 ms 14156 KB Output is correct
22 Correct 252 ms 14456 KB Output is correct
23 Correct 244 ms 14028 KB Output is correct
24 Correct 248 ms 14432 KB Output is correct
25 Correct 251 ms 14228 KB Output is correct
26 Correct 235 ms 14168 KB Output is correct
27 Correct 242 ms 14240 KB Output is correct
28 Incorrect 9 ms 7788 KB Output isn't correct
29 Halted 0 ms 0 KB -