Submission #414256

#	Time	Username	Problem	Language	Result	Execution time	Memory
414256		ACmachine	Swapping Cities (APIO20_swap)	C++17	100 / 100	292 ms	21816 KiB

swap

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

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i>=(k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9 + 7;
const ll INFF = (ll)1e18;
int n, m;
vector<vector<array<int, 2>>> merge_history;// ked sa mensi mergne do vacsieho, zapamatam si ze mensi -> merge vacsi; max logn krat sa potom nieco mergne; usortim podla casov;
// when comp became good 
vector<int> good_history;
struct dsu{
    vector<int> p;
    vector<bool> good;
    vector<int> deg;
    int counter = -1;
    dsu(int n){
        deg.resize(n, 0);
        p.resize(n, -1);
        good.resize(n, false);
    }
    int find(int x){
        return (p[x] < 0 ? x : p[x] = find(p[x]));
    }
    bool same_set(int u, int v){
        return find(u) == find(v);
    }
    bool join(int u, int v){
        counter++;
        deg[u]++; deg[v]++; 
        bool dgood = ((deg[u] > 2 || deg[v] > 2) ? true : false);
        u = find(u);
        v = find(v);
        if(u == v){
            if(!good[u]){
                good_history[u] = counter;
                good[u] = true;
            }
            return false;
        } 
        if(-p[u] < -p[v])
            swap(u, v);
        if(!good[u] && (dgood || good[v])){
            good[u] = true;
            good_history[u] = counter;
        }
        p[u] += p[v]; p[v] = u;
        merge_history[v].pb({counter, u});
        return true;
    }
};
vector<array<int, 3>> edges;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M;
    good_history.resize(n, -1);
    merge_history.resize(n);
    REP(i, m){
        edges.pb({W[i], U[i], V[i]});
    }
    sort(edges.begin(), edges.end());
    dsu d(n);
    for(auto e : edges){
        d.join(e[1], e[2]);
    } 
}

int getMinimumFuelCapacity(int u, int v) { 
    int ans = INF;
    int curr_time = 0;
    bool fn = false;
    while(true){
        array<int, 2> tm = {curr_time, -1};
        auto it = lower_bound(merge_history[u].begin(), merge_history[u].end(), tm);
        auto it2 = lower_bound(merge_history[v].begin(), merge_history[v].end(), tm);
        int tf = INF;
        int ts = INF; 
        if(it != merge_history[u].end())
            tf = (*it)[0];
        if(it2 != merge_history[v].end())
            ts = (*it2)[0];
        if(tf == ts && tf == INF)
            break; 
        if(tf == ts){
            curr_time = tf + 1;
            u = (*it)[1];
            v = (*it)[1]; 
        }
        else if(tf < ts){
            curr_time = tf + 1;
            u = (*it)[1];
        }
        else{
            curr_time = ts + 1;
            v = (*it2)[1];
        }
        if(u == v){
            if(good_history[u] != -1){
                fn = true;
                ans = min(ans, max(edges[good_history[u]][0], edges[curr_time - 1][0]));
            }
        }
    } 
    if(ans == INF)
        return -1;
    return ans; 
}

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:75:10: warning: variable 'fn' set but not used [-Wunused-but-set-variable]
   75 |     bool fn = false;
      |          ^~

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