Submission #651484

#	Time	Username	Problem	Language	Result	Execution time	Memory
651484		perchuts	Swapping Cities (APIO20_swap)	C++17	43 / 100	308 ms	35800 KiB

swap

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<tuple<int,int,int>>edges;

int lvl[maxn], par[maxn], when[maxn];

ii pontas[maxn];

vector<int>comp[maxn];
vector<ii>parents[maxn];

int findp(int x){return par[x] = (par[x]==x?x:findp(par[x]));}

void merge(int w,int u,int v){
    int pu = findp(u), pv = findp(v), ciclo = 0;
    if(lvl[pu]<lvl[pv])swap(pu,pv), swap(u,v);
    if(pu==pv)ciclo = 1;
    //check if someone's component turned into a non-path component
    par[pv] = pu;  
    if(when[pu]==inf&&when[pv]!=inf){
        for(auto x:comp[pu])when[x] = w;
    }else if(when[pu]!=inf&&when[pv]==inf){
        for(auto x:comp[pv])when[x] = w;
    }else if((ciclo||(u!=pontas[pu].first&&u!=pontas[pu].second)||
    (v!=pontas[pv].first&&v!=pontas[pv].second))&&when[pu]==inf&&
    when[pv]==inf){
        for(auto x:comp[pu])when[x] = w;
        if(!ciclo)for(auto x:comp[pv])when[x] = w;
    }
    if(ciclo)return;
    for(auto x:comp[pv]){
        comp[pu].pb(x);
        parents[x].pb({w,pu});
    }
    if(when[pu]==when[pv]&&when[pu]==inf){
        if(pontas[pu].first==u)swap(pontas[pu].first,pontas[pu].second);
        if(pontas[pv].first!=v)pontas[pu].second = pontas[pv].first;
        else pontas[pu].second = pontas[pv].second;
    }
    if(lvl[pu]==lvl[pv])++lvl[pu];
}

void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {

    for(int i=0;i<M;++i){
        edges.pb({W[i], U[i], V[i]});
    }

    for(int i=0;i<N;++i){
        par[i] = i, pontas[i] = {i,i}, when[i] = inf;
        parents[i].pb({0,i}), comp[i].pb(i);
    }

    sort(all(edges));

    for(auto [w,u,v]:edges){
        merge(w,u,v);
    }
    
    for(int i=0;i<N;++i)reverse(all(parents[i]));
}

int getMinimumFuelCapacity(int X, int Y) {
    if(when[X]==inf)return -1;
    int last = 0;
    while(last!=min(sz(parents[X]), sz(parents[Y]))-1){
        if(parents[X][last]!=parents[Y][last])break;
        ++last;
    }
    auto [custo,pai] = parents[X][last];
    assert(pai==parents[Y][last].second);
    ckmax(custo, parents[Y][last].first);
    return max(custo, min(when[X], when[Y]));
}

// int main() {
//   int N, M; 
//   assert(2 == scanf("%d %d", &N, &M));
  
//   std::vector<int> U(M), V(M), W(M);
//   for (int i = 0; i < M; ++i) {
//     assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
//   }

//   int Q;
//   assert(1 == scanf("%d", &Q));

//   std::vector<int> X(Q), Y(Q);
//   for (int i = 0; i < Q; ++i) {
//     assert(2 == scanf("%d %d", &X[i], &Y[i]));
//   }

//   init(N, M, U, V, W);
  
//   std::vector<int> minimum_fuel_capacities(Q);
//   for (int i = 0; i < Q; ++i) {
//     minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
//   }

//   for (int i = 0; i < Q; ++i) {
//     printf("%d\n", minimum_fuel_capacities[i]);
//   }
  
//   return 0;
// }

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