Submission #395294

#	Time	Username	Problem	Language	Result	Execution time	Memory
395294		abc864197532	Swapping Cities (APIO20_swap)	C++17	37 / 100	2097 ms	10612 KiB

swap

#include <bits/stdc++.h>
// #include "grader_swap.cpp"
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, Doludu = 123, N = 100001, logN = 18, K = 40;

int n, m;
vector <int> dsu, tag, deg, mx;

void init() {
    dsu.assign(n, 0);
    deg.assign(n, 0);
    tag.assign(n, false);
    mx.assign(n, 0);
    iota(all(dsu), 0);
}

int Find(int v) {
    if (dsu[v] == v) return v;
    return dsu[v] = Find(dsu[v]);
}

bool Union(int u, int v) {
    int nu = Find(u), nv = Find(v);
    if (nu == nv) {
        tag[nu] = true;
        return false;
    }
    deg[u]++, deg[v]++;
    mx[nu] = max(mx[nu], deg[u]);
    mx[nv] = max(mx[nv], deg[v]);
    dsu[nu] = nv;
    mx[nv] = max(mx[nv], mx[nu]);
    if (tag[nu]) tag[nv] = true;
    return true;
}

vector <int> u, v, w, p;

void init(int _n, int _m, vector <int> _u, vector <int> _v, vector <int> _w) {
    n = _n, m = _m, u = _u, v = _v, w = _w;
    p.resize(m);
    iota(all(p), 0);
    sort(all(p), [&](int i, int j) {
        return w[i] < w[j];
    });
}

int getMinimumFuelCapacity(int U, int V) {
    vector <int> cnt(n, 0);
    init();
    for (int i : p) {
        Union(u[i], v[i]);
        if (Find(U) == Find(V) && (tag[Find(U)] || mx[Find(V)] > 2)) {
            return w[i];
        }
    }
    return -1;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
2 3 3
1 4 10
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2
 */

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27