Submission #1310251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310251		M_SH_O	자매 도시 (APIO20_swap)	C++20	13 / 100	177 ms	10624 KiB

swap

/*#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/
#include <bits/stdc++.h>
#include "swap.h"
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
//#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
//using namespace __gnu_pbds;

const ll INF = 1e18+7;
const int lg = 20;
//const ll MOD = 1e9+7;
const ll MOD2 = 998244353;

mt19937 rng(1488);
ll randll(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

vpll p;
vll s, cnt;

ll find(ll v, ll t) {
    if (p[v].fr == v || p[v].se > t) return v;
    return find(p[v].fr, t);
}

void unite(ll a, ll b, ll t, bool q) {
    a = find(a, t);
    b = find(b, t);

    if (a == b) {
        cnt[a] = min(cnt[a], t);
        return;
    }

    if (s[a] < s[b]) {
        p[a] = {b, t};
        s[b] += s[a];
        cnt[b] = min(cnt[b], cnt[a]);
        if (q) cnt[b] = min(cnt[b], t);
    }
    else {
        p[b] = {a, t};
        s[a] += s[b];
        cnt[a] = min(cnt[b], cnt[a]);
        if (q) cnt[a] = min(cnt[a], t);
    }
}


void init(int n, int m, vi u, vi v, vi W) {
    vector<pair<ll, pll>> a(m);
    for (int i = 0; i < m; i ++) {
        a[i] = {W[i], {u[i], v[i]}};
    }
    sort(a);

    vll k(n+7, 0);
    p.clear();
    s.clear();
    cnt.clear();
    s.resize(n+7, 1);
    cnt.resize(n+7, INF);
    p.resize(n+7);
    for (int i = 0; i <= n; i ++) {
        p[i] = {i, -1};
    }
    for (auto i : a) {
        k[i.se.fr] ++;
        k[i.se.se] ++;

        unite(i.se.fr, i.se.se, i.fr, (k[i.se.se] >= 3 || k[i.se.fr] >= 3));
    }
}

int getMinimumFuelCapacity(int x, int y) {
    ll l = -1, r = 1e9+7;
    while (r-l > 1) {
        ll t = (l+r)/2;
        if (find(x, t) == find(y, t) && cnt[find(x, t)] <= t) r = t;
        else l = t;
    }
    if (r == 1e9+7) return -1;
    return r;
}


/*int main(){
    speed;
    srand(time(0));
    ll q;
    cin >> q;

    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});

    while (q --) {
        ll x, y;
        cin >> x >> y;
        cout << getMinimumFuelCapacity(x, y) << endl;
    }
}*/

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