Submission #734705

#	Time	Username	Problem	Language	Result	Execution time	Memory
734705		DrearyJoke	Swapping Cities (APIO20_swap)	C++17	100 / 100	398 ms	58756 KiB

swap

#include "swap.h"

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define END "\n"
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int> parent, sz;
void make_set(int n) {
    parent.resize(n);
    iota(all(parent), 0);
    sz.assign(n, 1);
}

int find_parent(int a) {
    if (a == parent[a]) return a;
    else return parent[a] = find_parent(parent[a]);
}

vector<vector<int>> adj;
vector<int> good, weight;

struct LCA {
    int n, d;
    vector<vector<int>> parent;
    vector<int> depth;
    LCA () {}
    LCA (const vector<vector<int>>& adj, int r) {
        n = adj.size();
        assert(r < adj.size());
        d = 0;
        while ((1 << d) <= n) d++;
        depth.resize(n);
        parent.resize(d, vector<int>(n));
        parent[0][r] = r;
        dfs(adj, r, -1);
        pre_calc();
    }
    void dfs(const vector<vector<int>>& adj, int v, int p) {
        // cout << "VISITING: " << v << " " << p << endl;
        for (auto u: adj[v]) {
            if (u != p) 
                parent[0][u] = v, depth[u] = depth[v] + 1, dfs(adj, u, v);
        }
    }
    void pre_calc() {
        for (int i = 1; i < d; ++i) {
            for (int j = 0; j < n; ++j) {
                parent[i][j] = parent[i - 1][parent[i - 1][j]];
            }
        }
    }
    int walk(int v, int x) {
        for (int i = d - 1; i >= 0; --i) {
            if (x & (1 << i)) v = parent[i][v];
        }
        return v;
    }
    int lca(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int x = depth[u] - depth[v];
        u = walk(u, x);
        if (u == v) return u;
        for (int i = d - 1; i >= 0; --i) {
            if (parent[i][u] != parent[i][v]) u = parent[i][u], v = parent[i][v];
        }
        return parent[0][u];
    }
};

LCA lca;
int root;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    make_set(N + M);
    adj.clear();
    adj.resize(N + M);
    vector<int> idxes(M);
    iota(all(idxes), 0);
    sort(all(idxes), [&] (int a, int b) {
        return W[a] < W[b];
    });
    int counter = N;
    good.resize(N + M), weight.resize(N + M);
    vector<int> degree(N);
    for (int i = 0; i < M; ++i) {
        int idx = idxes[i];
        int a = find_parent(U[idx]), b = find_parent(V[idx]), w = W[idx];
        ++degree[U[idx]];
        ++degree[V[idx]];
        int v = counter++;
        // cout << "ADDING EDGE: " << v << " " << a << " " << b << endl;
        adj[v].push_back(a);
        if (a != b) adj[v].push_back(b);
        if (a == b || good[a] || good[b] || degree[U[idx]] > 2 || degree[V[idx]] > 2) {
            good[v] = 1;
        }
        weight[v] = w;
        parent[a] = v;
        parent[b] = v;
    }
    assert(counter == N + M);
    lca = LCA(adj, counter - 1);
    // for (int i = 0; i < N + M; ++i) cout << i << ": " << lca.parent[0][i] << endl;
    root = counter - 1;
}

int getMinimumFuelCapacity(int X, int Y) {
    int V = lca.lca(X, Y);
    // cout << X << " " << Y << ": " << V << endl;
    if (good[V]) return weight[V];
    for (int i = lca.d - 1; i >= 0; --i) {
        if (!good[lca.parent[i][V]]) V = lca.parent[i][V]; 
    } 
    // cout << "FINAL: " << X << " " << Y << ": " << V << endl;
    if (V == root) return -1;
    return weight[lca.parent[0][V]];
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from swap.cpp:19:
swap.cpp: In constructor 'LCA::LCA(const std::vector<std::vector<int> >&, int)':
swap.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         assert(r < adj.size());
      |                ~~^~~~~~~~~~~~

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