Submission #736578

#	Time	Username	Problem	Language	Result	Execution time	Memory
736578		GusterGoose27	Swapping Cities (APIO20_swap)	C++17	50 / 100	382 ms	44072 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MAXM = 2e5;
const int inf = 1e9;

class edge {
public:
    int u, v, w;
    edge(int u, int v, int w) : u(u), v(v), w(w) {}
    edge() {}
};

bool operator<(edge &a, edge &b) {
    return (a.w == b.w) ? (a.u == b.u) ? (a.v < b.v) : (a.u < b.u) : (a.w < b.w);
}

edge edges[MAXM];
vector<pii> par[MAXN]; // time, val
vector<int> in_set[MAXN];
map<int, int> compress;
int comp_inv[MAXM];
int nice_pos[MAXN];
pii epoints[MAXN];
int t;

void merge(int a, int b) {
    int an = par[a].back().second;
    int bn = par[b].back().second;
    if (an == bn) {
        nice_pos[an] = min(nice_pos[an], t);
        return;
    }
    if (in_set[an].size() < in_set[bn].size()) {
        swap(a, b);
        swap(an, bn);
    }
    for (int v: in_set[bn]) {
        in_set[an].push_back(v);
        par[v].push_back(pii(t, an));
    }
    if ((a == epoints[an].first || a == epoints[an].second) && 
        (b == epoints[bn].first || b == epoints[bn].second)) {
        epoints[an] = pii(epoints[an].first+epoints[an].second-a, epoints[bn].first+epoints[bn].second-b);
    }
    else {
        nice_pos[an] = min(nice_pos[an], t);
    }
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    for (int i = 0; i < m; i++) edges[i] = edge(U[i], V[i], W[i]);
    sort(W.begin(), W.end());
    for (int w: W) {
        if (compress.find(w) == compress.end()) {
            compress[w] = compress.size();
            comp_inv[compress.size()-1] = w;
        }
    }
    for (int i = 0; i < m; i++) edges[i].w = compress[edges[i].w];
    sort(edges, edges+m);
    for (int i = 0; i < n; i++) {
        par[i].push_back(pii(-1, i));
        in_set[i].push_back(i);
        nice_pos[i] = inf;
        epoints[i] = pii(i, i);
    }
    int j = 0;
    for (int i = 0; i < compress.size(); i++) {
        t = i;
        while (j < m && edges[j].w == i) {
            merge(edges[j].u, edges[j].v);
            j++;
        }
    }
}

int get_par(int x, int cur) {
    int mn = 0;
    int mx = par[x].size();
    while (mx > mn+1) {
        int cval = (mn+mx)/2;
        if (par[x][cval].first <= cur) mn = cval;
        else mx = cval;
    }
    return par[x][mn].second;
}

int getMinimumFuelCapacity(int x, int y) {
    int mn = -1;
    int mx = compress.size();
    while (mx > mn+1) {
        int cur = (mn+mx)/2;
        int p1 = get_par(x, cur);
        int p2 = get_par(y, cur);
        if (p1 == p2 && nice_pos[p1] <= cur) mx = cur;
        else mn = cur;
    }
    if (mx == compress.size()) {
        return -1;
    }
    return comp_inv[mx];
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < compress.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:105:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     if (mx == compress.size()) {
      |         ~~~^~~~~~~~~~~~~~~~~~

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