Submission #1165644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165644		SmuggingSpun	Swapping Cities (APIO20_swap)	C++20	7 / 100	275 ms	50844 KiB

swap

#include<bits/stdc++.h>
#include "swap.h"
using namespace std;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
template<class T>void maximize(T& a, T b){
    if(a < b){
        a = b;
    }
}
const int lim = 1e5 + 5;
const int INF = 1e9;
bool is_sub2;
int n, m, u[lim << 1], v[lim << 1], w[lim << 1];
vector<int>g[lim];
namespace sub2{
    int third;
    void init(){
        if(n > 3){
            vector<int>p(n - 1);
            iota(p.begin(), p.end(), 1);
            sort(p.begin(), p.end(), [&] (int i, int j){
                return w[g[i][0]] < w[g[j][0]];
            });
            third = p[2];
        }
    }
}
namespace sub5{
    int h[lim], up[lim][17], mx[lim][17], mi[lim][17];
    vector<pair<int, int>>opt[lim];
    void dfs_1(int s, int p = -1){
        for(int& i : g[s]){
            int d = u[i] ^ v[i] ^ s;
            if(d != p){
                h[d] = h[up[d][0] = s] + 1;
                mx[d][0] = w[i];
                for(int i = 1; i < 17; i++){
                    up[d][i] = up[up[d][i - 1]][i - 1];
                    mx[d][i] = max(mx[d][i - 1], mx[up[d][i - 1]][i - 1]);
                }
                dfs_1(d, s);
                opt[s].emplace_back(w[i], d);
            }
        }
    }
    void dfs_2(int s, int p = -1){
        sort(opt[s].begin(), opt[s].end());
        while(opt[s].size() < 4){
            opt[s].emplace_back(INF, -1);
        }
        for(int& i : g[s]){
            int d = u[i] ^ v[i] ^ s;
            if(d != p){
                for(int j = 0; true; j++){
                    if(opt[s][j].second != d){
                        mi[d][0] = opt[s][j].first;
                        for(int k = 1; k < 17; k++){
                            mi[d][k] = min(mi[d][k - 1], mi[up[d][k - 1]][k - 1]);
                        }
                        dfs_2(d, s);
                        break;
                    }
                }
            }
        }
    }
    int lca(int u, int v){
        for(int i = 0, k = h[u] - h[v]; i < 17; i++){
            if(1 << i & k){
                u = up[u][i];
            }
        }
        if(u == v){
            return u;
        }
        for(int i = 16; i > -1; i--){
            if(up[u][i] != up[v][i]){
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
    int query(int u, int v){
        if(h[u] < h[v]){
            swap(u, v);
        }
        int root = lca(u, v), ans_max = 0, ans_min = INF, ut = u, vt = v;
        for(int i = 0, uk = u, vk = v, ku = h[u] - h[root], kv = h[v] - h[root], tu = h[u] - h[root] - 1, tv = h[v] - h[root] - 1; i < 17; i++){
            if(1 << i & ku){
                maximize(ans_max, mx[uk][i]);
                uk = up[uk][i];
            }
            if(1 << i & kv){
                maximize(ans_max, mx[vk][i]);
                vk = up[vk][i];
            }
            if(tu > 0 && (1 << i & tu)){
                minimize(ans_min, mi[ut][i]);
                ut = up[ut][i];
            }
            if(tv > 0 && (1 << i & tv)){
                minimize(ans_min, mi[vt][i]);
                vt = up[vt][i];
            }
        }
        if(root != v){
            for(auto& [val, vertex] : opt[root]){
                if(vertex != ut && vertex != vt){
                    minimize(ans_min, val);
                    break;
                }
            }
        }
        else{
            bool flag = true;
            for(auto& [val, vertex] : opt[root]){
                if(vertex != ut && (flag = !flag)){
                    minimize(ans_min, val);
                    break;
                }
            }
        }
        return max(ans_max, ans_min);
    }
    void init(){
        memset(up, 0, sizeof(up));
        memset(mx, 0, sizeof(mx));
        memset(mi, 0x3f, sizeof(mi));
        dfs_1(0);
        dfs_2(0);
    }
}
void init(int N, int M, vector<int>U, vector<int>V, vector<int>W){
    n = N;
    m = M;
    for(int i = 0; i < m; i++){
        g[u[i] = U[i]].emplace_back(i);
        g[v[i] = V[i]].emplace_back(i);
        w[i] = W[i];
    }
    // sub5::init();
    if(m == n - 1){
        sub5::init();
        return;
    }
    if(is_sub2 = (*max_element(u, u + m) == 0 && m == n - 1)){
        sub2::init();
        return;
    }
}
int getMinimumFuelCapacity(int x, int y){
    if(false){
        if(x == 0){
            return n < 4 ? -1 : max(w[g[y][0]], w[g[sub2::third][0]]);
        }
        return n < 4 ? -1 : max({w[g[x][0]], w[g[y][0]], w[g[sub2::third][0]]});
    }
    if(m == n - 1){
        int ans = sub5::query(x, y);
        return ans >= INF ? -1 : ans;
    }
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:167:1: warning: control reaches end of non-void function [-Wreturn-type]
  167 | }
      | ^

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