Submission #1077920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077920		GrindMachine	Swapping Cities (APIO20_swap)	C++17	30 / 100	2053 ms	57492 KiB

swap

#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define ff first
#define ss second
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
 
template<typename T>
void amin(T &x, T y){
    x = min(x,y);
}
 
template<typename T>
void amax(T &x, T y){
    x = max(x,y);
}
 
template<typename A,typename B>
string to_string(pair<A,B> p);
 
string to_string(const string &s){
    return "'"+s+"'";
}
 
string to_string(const char* s){
    return to_string((string)s);
}
 
string to_string(bool b){
    return b?"true":"false";
}
 
string to_string(vector<bool> v){
    string res = "{";
    rep(i,sz(v)){
        res += to_string(v[i])+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}
 
template<typename A>
string to_string(A v){
    string res = "{";
    trav(x,v){
        res += to_string(x)+",";
    }
    if(res.back() == ',') res.pop_back();
    res += "}";
    return res;
}
 
template<typename A,typename B>
string to_string(pair<A,B> p){
    return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}
 
#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl
 
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;
 
#include "swap.h"
 
vector<int> par(N);
 
int find(int u){
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}
 
void merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    par[v] = u;
}
 
vector<pii> adj1[N], adj2[N];

const int LOG = 17;

int up[N][LOG], mxw[N][LOG];
vector<int> depth(N);
vector<int> subsiz(N);

void dfs1(int u, int p){
    subsiz[u] = 1;
    for(auto [v,w] : adj1[u]){
        if(v == p) conts;
        depth[v] = depth[u]+1;
        up[v][0] = u;
        mxw[v][0] = w;
        rep1(j,LOG-1){
            up[v][j] = up[up[v][j-1]][j-1];
            mxw[v][j] = max(mxw[v][j-1],mxw[up[v][j-1]][j-1]);
        }
        dfs1(v,u);
        subsiz[u] += subsiz[v];
    }
}
 
int lift(int u, int k){
    rep(j,LOG){
        if(k&(1<<j)){
            u = up[u][j];
        }
    }
    return u;
}
 
int get_lca(int u, int v){
    if(depth[u] < depth[v]) swap(u,v);
    int k = depth[u]-depth[v];
    u = lift(u,k);
    if(u == v) return u;
 
    rev(j,LOG-1,0){
        if(up[u][j] != up[v][j]){
            u = up[u][j];
            v = up[v][j];
        }
    }
 
    u = up[u][0], v = up[v][0];
    assert(u == v);
    return u;
}

int get_mx(int u, int k){
    int mx = -inf1;
    rep(j,LOG){
        if(k&(1<<j)){
            amax(mx,mxw[u][j]);
            u = up[u][j];
        }
    }
    return mx;
}

vector<int> best(N,inf1);
vector<int> smallest_cyc(N,inf1);
vector<int> enter[N], leave[N];
multiset<int> ms[N];

void dfs2(int u, int p){
    pii best = {-1,-1};
    for(auto [v,w] : adj1[u]){
        if(v == p) conts;
        pii px = {subsiz[v],v};
        amax(best,px);
    }

    int heavy = best.ss;
    if(heavy != -1){
        dfs2(heavy,u);
        swap(ms[u],ms[heavy]);
    }

    for(auto [v,w] : adj1[u]){
        if(v == p or v == heavy) conts;
        trav(x,ms[v]){
            ms[u].insert(x);
        }
        ms[v].clear();
    }

    if(!ms[u].empty()){
        amin(smallest_cyc[u],*ms[u].begin());
    }

    trav(x,enter[u]){
        amin(smallest_cyc[u],x);
        ms[u].insert(x);
    }

    trav(x,leave[u]){
        rep1(iter,2){
            ms[u].erase(ms[u].find(x));
        }
    }
}

void init(int n, int m,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    
    vector<array<int,3>> edges;
    rep(i,m){
        edges.pb({W[i],U[i],V[i]});
    }
 
    sort(all(edges));
    vector<array<int,3>> span, non_span;
    iota(all(par),0);
 
    for(auto [w,u,v] : edges){
        if(find(u) != find(v)){
            span.pb({u,v,w});
            merge(u,v);
        }
        else{
            non_span.pb({u,v,w});
        }
    }
 
    for(auto [u,v,w] : span){
        adj1[u].pb({v,w}), adj1[v].pb({u,w});
    }
 
    for(auto [u,v,w] : non_span){
        adj2[u].pb({w,v}), adj2[v].pb({w,v});
    }
    
    dfs1(0,-1);
    
    rep(u,n){
        for(auto [v,w] : adj1[u]){
            adj2[u].pb({w,v});
        }
 
        sort(all(adj1[u]));
        sort(all(adj2[u]));
    }

    priority_queue<pii,vector<pii>,greater<pii>> pq;
    rep(i,n){
        if(sz(adj2[i]) >= 3){
            int val = 0;
            rep(j,3){
                amax(val,adj2[i][j].ff);
            }

            pq.push({val,i});
        }
    }

    vector<bool> vis(n);

    while(!pq.empty()){
        auto [cost,u] = pq.top();
        pq.pop();

        if(vis[u]) conts;
        vis[u] = 1;
        best[u] = cost;

        for(auto [w,v] : adj2[u]){
            pq.push({max(cost,w),v});
        }
    }

    for(auto [u,v,w] : non_span){
        int lca = get_lca(u,v);
        enter[u].pb(w), enter[v].pb(w);
        leave[lca].pb(w);
    }

    dfs2(0,-1);
}
 
int getMinimumFuelCapacity(int u, int v) {
    if(depth[u] > depth[v]) swap(u,v);
    int lca = get_lca(u,v);
 
    int du = depth[u]-depth[lca];
    int dv = depth[v]-depth[lca];
    int pmx = max(get_mx(u,du),get_mx(v,dv));
    
    int mn = min({best[u],best[v],smallest_cyc[u],smallest_cyc[v]});

    int ans = max(pmx,mn);
    if(ans == inf1) ans = -1;
 
    return ans;
}

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