Submission #725774

#	Time	Username	Problem	Language	Result	Execution time	Memory
725774		Cookie	Swapping Cities (APIO20_swap)	C++14	100 / 100	347 ms	61876 KiB

swap

#include<bits/stdc++.h>
using namespace std;
#include "swap.h"

#include <cassert>
#include <cstdio>
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector

#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int mxn = 3e5 + 5;
struct E{
    int u, v, w;
    bool operator <(const E &b){
        return(w < b.w);
    }
};
int p[mxn + 1], best[mxn + 1], in[mxn + 1], id = 0, val[mxn + 1], dep[mxn + 1], up[mxn + 1][19];
bool ok[mxn + 1];
vt<int>adj[mxn + 1];
vt<E>edge;
int fp(int u){
    if(p[u] == u)return(u);
    return(p[u] = fp(p[u]));
}
void unon(int a, int b, int w){
    bool valid = (in[a] >= 3 || in[b] >= 3);
    a = fp(a); b = fp(b);
    valid |= (ok[a] || ok[b]);
    int pos = ++id; p[pos] = pos; val[pos] = w;
    if(a == b){
        // cycle 
        ok[pos] = 1;
        adj[pos].pb(a); p[a] = pos;
        return;
    }
    ok[pos] = valid;
    adj[pos].pb(a); adj[pos].pb(b); p[a] = p[b] = pos;
    val[pos] = w;
}
void dfs(int s, int mn){
    if(ok[s])mn = min(mn, val[s]);
    best[s] = mn;
    for(auto i: adj[s]){
        dep[i] = dep[s] + 1;
        up[i][0] = s;
        dfs(i, mn);
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v])swap(u, v);
    int k = dep[u] - dep[v];
    for(int i = 0; i < 19; i++){
        if(k & (1 << i)){
            u = up[u][i];
        }
    }
    if(u == v)return(u);
    for(int i = 18; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i]; v = up[v][i];
        }
    }
    
    return(up[u][0]);
}
void init(int n, int m, vt<int>u, vt<int>v, vt<int>w){
     for(int i = 0; i < m; i++){
         edge.pb({u[i], v[i], w[i]});
     }
     id = n - 1;
     sort(edge.begin(), edge.end());
     for(int i = 0; i < n; i++){
         p[i] = i;
     }
     for(auto [u, v, w]: edge){
         
         in[u]++; in[v]++;
         unon(u, v, w);
     }
     dfs(id, 1e9 + 1);
     for(int i = 1; i < 19; i++){
         for(int j = 0; j <= id; j++){
             up[j][i] = up[up[j][i - 1]][i - 1];
         }
     }
}
int getMinimumFuelCapacity(int x, int y){
    int l = lca(x, y);
    if(best[l] == 1e9 + 1)return(-1);
    return(best[l]);
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:83:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |      for(auto [u, v, w]: edge){
      |               ^

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