Submission #428608

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
428608	2021-06-15T13:12:51 Z	snasibov05	Swapping Cities (APIO20_swap)	C++14	Compilation error	0 ms	0 KB

swap

#include "swap.h"
#include <vector>
#include <queue>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define oo 1000000001

struct edge{
    int u, v;
    int cost;

    bool operator< (edge e) const{
        return cost < e.cost;
    }
};


vector<int> pr;
vector<int> sz;
vector<bool> possible;
vector<edge> ed;
vector<int> deg;

int Find(int u){
    if (pr[u] == u) return u;
    else return pr[u] = Find(pr[u]);
}

void Union(int u, int v){
    deg[u]++; deg[v]++;

    int x = Find(u);
    int y = Find(v);

    if (x == y){
        possible[x] = true;
        return;
    }

    if (sz[x] < sz[y]) swap(x, y);

    sz[x] += sz[y];
    pr[y] = x;

    possible[x] = possible[y] | possible[x];
    if (deg[u] >= 3 || deg[v] >= 3) possible[x] = true;
}

bool check(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y && possible[x]) return true;
    else return false;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    pr.resize(n);
    sz.resize(n);
    possible.resize(n);
    ed.resize(m);
    deg.resize(n);

    for (int i = 0; i < m; ++i) {
        ed[i].u = u[i];
        ed[i].v = v[i];
        ed[i].cost = w[i];
    }

    sort(ed.begin(), ed.end());

}

int getMinimumFuelCapacity(int x, int y) {

    int n = pr.size();
    int m = ed.size();
    int ans = -1;

    for (int i = 0; i < n; ++i) {
        pr[i] = i;
        sz[i] = 1;
        possible[i] = false;
        deg[i] = 0;
    }



    for (int i = 0; i < m; ++i) {
        Union(ed[i].u, ed[i].v);
        if (check(x, y)) {
            ans = ed[i].cost;
            break;
        }
    }

    return ans;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:75:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   75 |     sort(ed.begin(), ed.end());
      |     ^~~~
      |     short