Submission #1041844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041844		KasymK	Swapping Cities (APIO20_swap)	C++17	37 / 100	2077 ms	12740 KiB

swap

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int MOD = 1e9+7;
const int INF = 1e9;
const int MAXN = 2e5+5;
vector<pair<int, pii>> v;
int n, m, rep[MAXN], sz[MAXN], deg[MAXN], cnt[MAXN];

int find(int x){
    if(rep[x] == x)
        return x;
    return rep[x] = find(rep[x]); // path compression
}

bool check(int x, int y){
    return (find(x) == find(y));
}

void merge(int x, int y){
    if(check(x, y))
        return;
    x = find(x), y = find(y);
    if(sz[x] > sz[y])
        swap(x, y);
    sz[y] += sz[x];
    rep[x] = y;
}

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)
        v.pb({U[i], {V[i], W[i]}});
    auto cmp = [&](pair<int, pii>  a, pair<int, pii> b) -> bool {
        return (a.ss.ss < b.ss.ss);
    };
    sort(all(v), cmp);
}

int getMinimumFuelCapacity(int x, int y){
    int l = 2, r = m-1, ans = -1;
    while(l <= r){
        int mid = (l+r)/2;
        for(int i = 0; i < n; ++i)
            cnt[i] = 0, deg[i] = 0, rep[i] = i, sz[i] = 1;
        for(int i = 0; i <= mid; ++i){
            merge(v[i].ff, v[i].ss.ff);
            deg[v[i].ff]++, deg[v[i].ss.ff]++;
        }
        int ok = 0, mx = 0;
        for(int i = 0; i < n; ++i){
            if(!check(i, x))
                continue;
            cnt[deg[i]]++;
            umax(mx, deg[i]);
        }
        if(mx <= 2 and cnt[1] == 2)
            ok = 1;
        if(check(x, y) and !ok)
            ans = mid, r = mid-1;
        else
            l = mid+1;
    }
    int answer = 0;
    if(ans == -1)
        answer = -1;
    else
        answer = v[ans].ss.ss;
    return answer;
}

// int main(){
//     int AD;
//     scanf("%d", &AD);
//     init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
//     while(AD--){
//         int x, y;
//         scanf("%d%d", &x, &y);
//         int answer = getMinimumFuelCapacity(x, y);
//         printf("%d\n", answer);
//     }
//     return 0;
// }

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