Submission #764603

#	Time	Username	Problem	Language	Result	Execution time	Memory
764603		raysh07	Swapping Cities (APIO20_swap)	C++17	0 / 100	96 ms	23956 KiB

swap

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

struct edge{
    int u, v, w;
};

bool comp(edge x, edge y){
    return x.w < y.w;
}
 
int n, m;
const int maxn = 1e5 + 69;
vector <pair<int, int>> adj[maxn];
int root[maxn], mn[maxn];
set <pair<int, pair<int, int>>> path, ans;
edge e[2 * maxn];
int mp[maxn];

int find(int x) {
    if (x == root[x]) return x;
    return root[x] = find(root[x]);
}

bool unite(int x, int y){
    x = find(x); y = find(y);
    if (x == y) return false;
    
    root[y] = x;
    return true;
}

pair<int, pair<int, int>> get(int u, int v, int w){
    return {w, {u, v}};
}

void dfs(int u, int need, int par){
    if (need == u) ans = path;
    for (auto [v, w] : adj[u]){
        if (v == par) continue;
        path.insert(get(u, v, w));
        path.insert(get(v, u, w));
        dfs(v, need, u);
        path.erase(get(u, v, w));
        path.erase(get(v, u, w));
    }
}
 
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    vector <pair<int, pair<int, int>>> vec;
    for (int i = 0; i < m; i++){
        vec.push_back({W[i], {U[i], V[i]}});
    }
    sort(vec.begin(), vec.end());
    
    for (int i = 0; i < m; i++){
        e[i].u = vec[i].second.first; 
        e[i].v = vec[i].second.second; 
        e[i].w = vec[i].first;
    }
    
    for (int i = 0; i < n; i++){
        root[i] = i;
        mn[i] = 1e9 + 1;
    }
    
    for (auto x : e){
        if (unite(x.u, x.v)){
            adj[x.u].push_back({x.v, x.w});
            adj[x.v].push_back({x.u, x.w});
        } else {
            mn[x.u] = min(mn[x.u], x.w);
            mn[x.v] = min(mn[x.v], x.w);
        }
    }
}
 
int getMinimumFuelCapacity(int x, int y) {
    dfs(x, y, -1);
    for (int i = 0; i < n; i++) mp[i] = 0;
    int lol = 0;
    for (auto x : ans) {
        lol = max(lol, x.first);
        mp[x.second.first]++;
        mp[x.second.second]++;
    }
    int l1 = 1e9 + 1;
    
    for (int i = 0; i < m; i++){
        if (ans.find(get(e[i].u, e[i].v, e[i].w)) == ans.end()){
            if (mp[e[i].u] || mp[e[i].v]) l1 = min(l1, e[i].w);
        }
    }
    
    if (l1 > 1e9) return -1;
    if (m == n - 1) assert(false);
    else return max(l1, lol);
}

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