Submission #1190412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190412		Br3ad	Swapping Cities (APIO20_swap)	C++20	37 / 100	2094 ms	8124 KiB

swap

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 1e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

struct DSU{
    vector<int> parent, edge_cnt;
    vector<bool> swappable;

    DSU(int n){
        parent = vector<int>(n+1);
        iota(all(parent), 0);

        edge_cnt = vector<int>(n+1, 0);
        swappable = vector<bool>(n+1, false);
    }

    int find_parent(int p){
        return (parent[p] == p)? p : parent[p] = find_parent(parent[p]);
    }

    void merge(int a, int b){
        int pa = find_parent(a);
        int pb = find_parent(b);
        edge_cnt[a]++;
        edge_cnt[b]++;

        // Degree >= 3
        if(edge_cnt[a] >= 3) swappable[pa] = true;
        if(edge_cnt[b] >= 3) swappable[pb] = true;

        // Contains cycle
        if(pa == pb) swappable[pb] = true;

        parent[pa] = pb;
        if(swappable[pa]) swappable[pb] = true;
    }

    bool check(int a, int b){
        int pa = find_parent(a);
        int pb = find_parent(b);
        return (pa == pb && swappable[pa]);
    }
};

int _n, _m;
vector<tuple<int, int, int>> edge;
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    _n = n;
    _m = m;
    for(int i = 0; i < m; i++) edge.PB({w[i], u[i], v[i]});
    sort(all(edge));
}

int getMinimumFuelCapacity(int x, int y){
    DSU dsu(_n);
    for(int i = 0; i < _m; i++){
        auto [w, u, v] = edge[i];
        dsu.merge(u, v);
        if(dsu.check(x, y)) return w;
    }
    return -1;
}

// int main(){
//     
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     
//     // ifstream cin();
//     // ofstream cout();
//     
//     vector<int> u = {0, 0, 1, 1, 1, 2};
//     vector<int> v = {1, 2, 2, 3, 4, 3};
//     vector<int> w = {4, 4, 1, 2, 10, 3};
//     init(5, 6, u, v, w);
// 
//     int ans1 = getMinimumFuelCapacity(1, 2);
//     int ans2 = getMinimumFuelCapacity(2, 4);
//     int ans3 = getMinimumFuelCapacity(0, 1);
//     cout << ans1 << endl << ans2 << endl << ans3 << endl;
//     
// }

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