Submission #576579

#	Time	Username	Problem	Language	Result	Execution time	Memory
576579		radal	Swapping Cities (APIO20_swap)	C++17	0 / 100	268 ms	35936 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
#pragma GCC target("sse,sse2,sse4,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
//    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
vector<int> pr[N],comp[N],adj[N];
int mi[N],n,m;
vector<pair<int,pll> > e;
void init (int nn,int mm,vector<int> U,vector<int> V,vector<int> W){
    n = nn;
    m = mm;
    rep(i,1,n+1){
        pr[i].pb(i);
        comp[i].pb(i);
        mi[i] = inf;
    }
    rep(i,0,m){
        U[i]++;
        V[i]++;
        e.pb({W[i],{U[i],V[i]}});
    }
    sort(all(e));
    rep(i,0,m){
        int x = e[i].Y.X,y = e[i].Y.Y;
        int u = pr[x].back(),v = pr[y].back();
        if (u != v){
            adj[x].pb(y);
            adj[y].pb(x);
            if (comp[u].size() > comp[v].size()) swap(u,v);
            while (!comp[u].empty()){
                int w = comp[u].back();
                comp[u].pop_back();
                pr[w].pb(v);
                comp[v].pb(w);
            }
            if (mi[u] < inf) mi[v] = min(mi[v],e[i].X);
            if (adj[x].size() >= 3 || adj[y].size() >= 3) mi[v] = min(mi[v],e[i].X);
        }
        else{
            mi[u] = min(mi[u],e[i].X);
        }
    }
}
int getMinimumFuelCapacity(int u, int v){
    u++;
    v++;
    int po1 = pr[u].size()-1,po2 = pr[v].size()-1;
    while (min(po1,po2) >= 1 && pr[u][po1-1] == pr[v][po2-1]) po1--,po2--;
    int calc = mi[pr[u][po1]];
    if (calc == inf) return -1;
    return calc;
}

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