oj.uz

Submission #697582

# Submission time Handle Problem Language Result Execution time Memory
697582 2023-02-10T12:28:43 Z whqkrtk04 Swapping Cities (APIO20_swap) C++17
0 / 100
 0 ms 212 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

struct UF {
    vector<int> P, A, B, C;

    int fin(int x) {
        if(P[x] == x) return x;
        else return P[x] = fin(P[x]);
    }

    int max_deg(int x) {
        return B[fin(x)];
    }

    void mer(int x, int y) {
        cout << x << " " << y << "\n";
        int xx = fin(x), yy = fin(y);
        if(xx != yy) P[yy] = xx;
        else C[xx] = 1;
        B[xx] = max(max(B[xx], B[yy]), max(++A[x], ++A[y]));
        C[xx] = C[xx] || C[yy];
    }

    UF(int n) {
        A.resize(n, 0), B.resize(n, 0), C.resize(n, 0);
        for(int i = 0; i < n; i++) P.push_back(i);
    }
};

int n, m;
vector<piii> E;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N, m = M, E.resize(M);
    for(int i = 0; i < M; i++) E[i] = {W[i], {U[i], V[i]}};
    sort(E.begin(), E.end());
}

int getMinimumFuelCapacity(int X, int Y) {
    UF uf(n);
    for(int i = 0; i < m; i++) {
        uf.mer(E[i].se.fi, E[i].se.se);
        //cout << uf.A << uf.B << uf.C << uf.P << "\n";
        if(uf.fin(X) == uf.fin(Y) && (uf.B[uf.fin(X)] >= 3 || uf.C[uf.fin(X)])) return E[i].fi;
    }
    return -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -