Submission #848917

#	Time	Username	Problem	Language	Result	Execution time	Memory
848917		tvladm2009	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int)1e9 + 7;
vector<int> t;
vector<int> dim;
vector<bool> is_line;
vector<int> when;
vector<bool> endpoint;
vector<int> when_join;
int n, m;

void clr() {
        t.resize(n + 1);
        dim.resize(n + 1);
        is_line.resize(n + 1);
        when.resize(n + 1);
        endpoint.resize(n + 1);
        when_join.resize(n + 1);
        for (int i = 1; i <= n; i++) {
                t[i] = i;
                dim[i] = 1;
                is_line[i] = 1;
                when_join[i] = 1;
                when[i] = -1;
        }
}

int root(int a) {
        if (a == t[a]) {
                return a;
        }
        else {
                return t[a];
        }
}

void join(int a, int b, int w) {
        int x = root(a);
        int y = root(b);
        if (a == b) {
                if (is_line[a] == 1) {
                        when[a] = val;
                }
                is_line[a] = 0;
                return;
        }
        if (dim[a] < dim[b]) {
                swap(a, b);
                swap(x, y);
        }
        if (is_line[a] && is_line[b] && endpoint[x] && endpoint[y]) {
                is_line[a] = 1;
                if (dim[a] > 1) {
                        endpoint[x] = 0;
                }
                if (dim[b] > 1) {
                        endpoint[y] = 0;
                }
        }
        else {
                if (is_line[a] == 1) {
                        when[a] = val;
                        is_line[a] = 0;
                }
        }
        when_join[b] = val;
        dim[a] += dim[b];
        t[b] = a;
}

struct Edge {
        int a;
        int b;
        int w;
};

bool operator < (Edge a, Edge b) {
        return a.w < b.w;
}

vector<Edge> edges;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
        assert((int)U.size() == M);
        assert((int)V.size() == M);
        assert((int)W.size() == M);
        
        n = N;
        m = M;
        edges.clear();
        for (int i = 0; i < m; i++) {
                edges.push_back({U[i], V[i], W[i]});
        }
        sort(edges.begin(), edges.end());
        clr();
        for (auto& edg : edges) {
                join(edg.a, edg.b, edg.w);
        }
}

int getMinimumFuelCapacity(int x, int y) {
        if (x == y) {
                return 0;
        }
        vector<int> path_x, path_y;
        while (1) {
                path_x.push_back(x);
                if (x == t[x]) {
                        break;
                }
                x = t[x];
        }
        while (1) {
                path_y.push_back(y);
                if (y == t[y]) {
                        break;
                }
                y = t[y];
        }
        reverse(path_x.begin(), path_x.end());
        reverse(path_y.begin(), path_y.end());
        bool deja = 0;
        int wjoin = 0;
        for (int i = max((int)path_x.size(), (int)path_y.size()) - 1; i >= 0; i--) {
                if (i < (int)path_x.size() && i < (int)path_y.size() && path_x[i] == path_y[i]) {
                        if (deja) {
                                return wjoin;
                        }
                        if (when[path_x[i]] != -1) {
                                return max(wjoin, when[path_x[i]]);
                        }
                }
                if (i < (int)path_x.size()) {
                        if (when[path_x[i]] != -1) {
                                deja = 1;
                        }
                        wjoin = max(wjoin, when[path_x[i]]);
                }
                if (i < (int)path_y.size()) {
                        if (when[path_y[i]] != -1) {
                                deja = 1;
                        }
                        wjoin = max(wjoin, when[path_y[i]]);
                }
        }
        return -1;
}

Compilation message (stderr)

swap.cpp: In function 'void join(int, int, int)':
swap.cpp:48:35: error: 'val' was not declared in this scope
   48 |                         when[a] = val;
      |                                   ^~~
swap.cpp:68:35: error: 'val' was not declared in this scope
   68 |                         when[a] = val;
      |                                   ^~~
swap.cpp:72:24: error: 'val' was not declared in this scope
   72 |         when_join[b] = val;
      |                        ^~~