Submission #723223

#	Time	Username	Problem	Language	Result	Execution time	Memory
723223		lukameladze	Swapping Cities (APIO20_swap)	C++14	100 / 100	675 ms	78556 KiB

swap

#include "swap.h"
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5, inf = 1e9;
int t,n,m,par[N],sz[N],is_chain[N],bec[N],in_deg[N],mx[N];
set < pii > s[N];
vector <int> comp[N];
struct edge {
    int x, y, c;
} a[N];
bool cmp(edge a, edge b) {
    return a.c < b.c;
}
void my_init() {
    for (int i = 1; i <= n; i++) {
        par[i] = i; sz[i] = 1; comp[i].pb(i); is_chain[i] = 1;
        s[i].insert({0, i});
        bec[i] = inf;
        is_chain[i] = 1;
    }
}
int get_col(int a) {
    return par[a];
}
void go(int a, int c){
    for (int x : comp[a]) {
        bec[x] = c;
    }
    is_chain[a] = false;
}
void col(int a, int b, int c) {
    a = get_col(a);
    b = get_col(b);
    if (a == b) {
        if (is_chain[a]) {
            go(a,c);
            is_chain[a] = false;
        }
        return ;   
    }
    if (sz[a] < sz[b]) swap(a,b);
    sz[a] += sz[b]; sz[b] = 0;
    mx[a] = max(mx[a], mx[b]);
    if (is_chain[a] && is_chain[b]) {
        if (mx[a] >= 3) {
            go(a,c); go(b,c);
        }
    } else
    if (is_chain[a] && !is_chain[b]) go(a,c), is_chain[a] = 0;
    else
    if (is_chain[b] && !is_chain[a]) go(b,c), is_chain[a] = 0;
    for (int vert : comp[b]) comp[a].pb(vert), par[vert] = a, s[vert].insert({c, a});//, cout<<vert<<" --- > "<<a<<" "<<c<<"dros\n";
    comp[b].clear();
}
int check(int mid, int a, int b) {
    int compa = (*(--s[a].upper_bound({mid,1e9}))).s;
    int compb = (*(--s[b].upper_bound({mid, 1e9}))).s;
    if (compa == compb && bec[a] <= mid && bec[b] <= mid) return 1;
    else return 0;
}
int solve(int x, int y) {
    int le = 1, ri = m, ans = 0;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if(check(mid, x,y)) {
            ans = mid;
            ri = mid - 1;
        } else le = mid + 1;
    }
    if (ans == 0) return -1;
    return a[ans].c;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M;
    for (int i = 1; i <= m; i++) {
//        cin>>a[i].x>>a[i].y>>a[i].c;
        a[i].x = U[i - 1] + 1; a[i].y = V[i - 1] + 1; a[i].c = W[i - 1];
    }
    sort(a + 1, a + m + 1, cmp);
    my_init();
    for (int i = 1; i <= m; i++) {
        in_deg[a[i].x]++; in_deg[a[i].y]++;
        mx[get_col(a[i].x)] = max(mx[get_col(a[i].x)], in_deg[a[i].x]);
        mx[get_col(a[i].y)] = max(mx[get_col(a[i].y)], in_deg[a[i].y]);
        col(a[i].x, a[i].y, i);
    }
    
}
int getMinimumFuelCapacity(int X, int Y) {
  int a = X + 1; int b = Y + 1;
  return solve(a,b);
}

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