Submission #983555

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
983555	2024-05-15T17:36:04 Z	RakhimovAmir	Swapping Cities (APIO20_swap)	C++14	Compilation error	0 ms	0 KB

swap

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

struct edge {
    ll w, x, y;
};

const ll N = 1e5 + 100, M = 30;
vector<pair<ll, ll>> g[N];
vector<edge> edges;
ll prt[N], a[N], b[N], p[N][M], mx[N][M], tin[N], tout[N], tt;
bool fl[N], visited[N];
vector<ll> v[N];

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

ll findParent(ll x) {
    if (prt[x] == x)
        return x;
    return prt[x] = findParent(prt[x]);
}

void addEdge(ll x, ll y, ll w) {
    g[x].push_back({w, y});
    g[y].push_back({w, x});
}

void merge(ll x, ll y, ll w) {
    ll X = prt[x], Y = prt[y];
    if (X == Y) {
        if (!fl[X])
            return;
        fl[X] = 0;
        for (auto i : v[X]) {
            if (i != X) {
                addEdge(X, i, w);
            }
        }
        return;
    }
    if (v[Y].size() > v[X].size()) {
        swap(x, y);
        swap(X, Y);
    }
    for (auto i : v[Y]) {
        v[X].push_back(i);
    }
    prt[Y] = X;
    if (!fl[X] || !fl[Y] || (x != a[X] && x != b[X]) || (y != a[Y] && y != b[Y])) {
        fl[X] = 0;
        addEdge(X, Y, w);
        return;
    } else {
        if (x == a[X]) {
            if (y == b[Y])
                a[X] = a[Y];
            else
                a[X] = b[Y];
        }
        else {
            if (y == b[Y])
                b[X] = a[Y];
            else
                b[X] = b[Y];
        }
    }
}

void dfs(ll x, ll par, ll w) {
    tin[x] = ++tt;
    visited[x] = 1;
    for (auto to : g[x]) {
        if (!visited[to.second])
          dfs(to.second, x, to.first);
    }
    p[x][0] = par;
    mx[x][0] = w;
    for (ll i = 1; i < M; i++) {
        p[x][i] = p[p[x][i - 1]][i - 1];
        mx[x][i] = max(mx[x][i - 1], mx[p[x][i - 1]][i - 1]);
        // cout << mx[x][i] << " " << x << " " << i << "\n";
    }
    tout[x] = tt;
}

ll ispr(ll x, ll y) {
    return tin[x] <= tin[y] && tout[x] >= tout[y];
}

ll lca(ll x, ll y) {
    if (ispr(x, y))
        return x;
    if (ispr(y, x))
        return y;
    for (ll i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y))
            x = p[x][i];
    }
    x = p[x][0];
    return x;
}

ll findMax(ll x, ll y) {
    ll ret = 0;
    if (x == y)
        return 0;
     for (ll i = M - 1; i >= 0; i--) {
        if (!ispr(p[x][i], y)) {
            ret = max(ret, mx[x][i]);
            x = p[x][i];
        }
    }
    ret = max(ret, mx[x][0]);
    return ret;
}

void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
    for (ll i = 0; i < N; i++) {
        prt[i] = i;
        a[i] = i;
        b[i] = i;
        fl[i] = 1;
        v[i].push_back(i);
    }
    for (ll i = 0; i < M; i++) {
        edges.push_back({W[i], U[i], V[i]});
    }
    sort(edges.begin(), edges.end(), cmp);
    for (auto i : edges) {
        merge(i.x, i.y, i.w);
    }

    for (ll i = 0; i < N; i++) {
        // ll pr = findParent(i);
        if (!visited[i]) {
            dfs(i, i, 0);
        }
    }
}

ll getMinimumFuelCapacity(ll X, ll Y) {
    ll P = lca(X, Y);
    if (!ispr(P, X) || !ispr(P, Y) || X == Y)
      return -1;
    return max(findMax(X, P), findMax(Y, P));
}

Compilation message

swap.cpp:6:5: error: 'll' does not name a type
    6 |     ll w, x, y;
      |     ^~
swap.cpp:9:7: error: 'll' does not name a type
    9 | const ll N = 1e5 + 100, M = 30;
      |       ^~
swap.cpp:10:13: error: 'll' was not declared in this scope
   10 | vector<pair<ll, ll>> g[N];
      |             ^~
swap.cpp:10:17: error: 'll' was not declared in this scope
   10 | vector<pair<ll, ll>> g[N];
      |                 ^~
swap.cpp:10:17: error: template argument 1 is invalid
swap.cpp:10:17: error: template argument 2 is invalid
swap.cpp:10:19: error: template argument 1 is invalid
   10 | vector<pair<ll, ll>> g[N];
      |                   ^~
swap.cpp:10:19: error: template argument 2 is invalid
swap.cpp:10:24: error: 'N' was not declared in this scope
   10 | vector<pair<ll, ll>> g[N];
      |                        ^
swap.cpp:12:1: error: 'll' does not name a type
   12 | ll prt[N], a[N], b[N], p[N][M], mx[N][M], tin[N], tout[N], tt;
      | ^~
swap.cpp:13:9: error: 'N' was not declared in this scope
   13 | bool fl[N], visited[N];
      |         ^
swap.cpp:13:21: error: 'N' was not declared in this scope
   13 | bool fl[N], visited[N];
      |                     ^
swap.cpp:14:8: error: 'll' was not declared in this scope
   14 | vector<ll> v[N];
      |        ^~
swap.cpp:14:10: error: template argument 1 is invalid
   14 | vector<ll> v[N];
      |          ^
swap.cpp:14:10: error: template argument 2 is invalid
swap.cpp:14:14: error: 'N' was not declared in this scope
   14 | vector<ll> v[N];
      |              ^
swap.cpp: In function 'bool cmp(edge, edge)':
swap.cpp:17:14: error: 'struct edge' has no member named 'w'
   17 |     return a.w < b.w;
      |              ^
swap.cpp:17:20: error: 'struct edge' has no member named 'w'
   17 |     return a.w < b.w;
      |                    ^
swap.cpp: At global scope:
swap.cpp:20:1: error: 'll' does not name a type
   20 | ll findParent(ll x) {
      | ^~
swap.cpp:26:6: error: variable or field 'addEdge' declared void
   26 | void addEdge(ll x, ll y, ll w) {
      |      ^~~~~~~
swap.cpp:26:14: error: 'll' was not declared in this scope
   26 | void addEdge(ll x, ll y, ll w) {
      |              ^~
swap.cpp:26:20: error: 'll' was not declared in this scope
   26 | void addEdge(ll x, ll y, ll w) {
      |                    ^~
swap.cpp:26:26: error: 'll' was not declared in this scope
   26 | void addEdge(ll x, ll y, ll w) {
      |                          ^~
swap.cpp:31:6: error: variable or field 'merge' declared void
   31 | void merge(ll x, ll y, ll w) {
      |      ^~~~~
swap.cpp:31:12: error: 'll' was not declared in this scope
   31 | void merge(ll x, ll y, ll w) {
      |            ^~
swap.cpp:31:18: error: 'll' was not declared in this scope
   31 | void merge(ll x, ll y, ll w) {
      |                  ^~
swap.cpp:31:24: error: 'll' was not declared in this scope
   31 | void merge(ll x, ll y, ll w) {
      |                        ^~
swap.cpp:72:6: error: variable or field 'dfs' declared void
   72 | void dfs(ll x, ll par, ll w) {
      |      ^~~
swap.cpp:72:10: error: 'll' was not declared in this scope
   72 | void dfs(ll x, ll par, ll w) {
      |          ^~
swap.cpp:72:16: error: 'll' was not declared in this scope
   72 | void dfs(ll x, ll par, ll w) {
      |                ^~
swap.cpp:72:24: error: 'll' was not declared in this scope
   72 | void dfs(ll x, ll par, ll w) {
      |                        ^~
swap.cpp:89:1: error: 'll' does not name a type
   89 | ll ispr(ll x, ll y) {
      | ^~
swap.cpp:93:1: error: 'll' does not name a type
   93 | ll lca(ll x, ll y) {
      | ^~
swap.cpp:106:1: error: 'll' does not name a type
  106 | ll findMax(ll x, ll y) {
      | ^~
swap.cpp:120:6: error: variable or field 'init' declared void
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |      ^~~~
swap.cpp:120:11: error: 'll' was not declared in this scope
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |           ^~
swap.cpp:120:17: error: 'll' was not declared in this scope
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |                 ^~
swap.cpp:120:30: error: 'll' was not declared in this scope
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |                              ^~
swap.cpp:120:32: error: template argument 1 is invalid
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |                                ^
swap.cpp:120:32: error: template argument 2 is invalid
swap.cpp:120:44: error: 'll' was not declared in this scope
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |                                            ^~
swap.cpp:120:46: error: template argument 1 is invalid
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |                                              ^
swap.cpp:120:46: error: template argument 2 is invalid
swap.cpp:120:58: error: 'll' was not declared in this scope
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |                                                          ^~
swap.cpp:120:60: error: template argument 1 is invalid
  120 | void init(ll N, ll M, vector<ll> U, vector<ll> V, vector<ll> W) {
      |                                                            ^
swap.cpp:120:60: error: template argument 2 is invalid
swap.cpp:144:1: error: 'll' does not name a type
  144 | ll getMinimumFuelCapacity(ll X, ll Y) {
      | ^~