Submission #486620

#	Time	Username	Problem	Language	Result	Execution time	Memory
486620		aryan12	Swapping Cities (APIO20_swap)	C++17	0 / 100	278 ms	58548 KiB

swap

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

const int MAXN = 1e5 + 5;
vector<array<int, 3> > edges(MAXN * 2);
int DP[20][MAXN * 3];
int depth[MAXN * 3];
vector<int> g[MAXN * 3];

struct ufds {
    bool isLine;
    pair<int, int> endpoints;
    int parent, value, depth;

    ufds(int x) {
        isLine = true;
        endpoints = {x, x};
        parent = x;
        value = 1e9;
        depth = 0;
    } 
} *Node[MAXN * 3];

int Find(int x) {
    if(Node[x]->parent == x) {
        return x;
    }
    return Node[x]->parent = Find(Node[x]->parent);
}

void Unite(int a, int b, int new_idx, int cur_val) {
    int original_a = a, original_b = b;
    a = Find(a);
    b = Find(b);
    Node[a]->parent = new_idx;
    Node[b]->parent = new_idx;
    g[new_idx].push_back(a);
    g[new_idx].push_back(b);
    Node[new_idx]->value = cur_val;
    DP[0][a] = new_idx;
    DP[0][b] = new_idx;
    if(a == b || !Node[a]->isLine || !Node[b]->isLine) {
        Node[new_idx]->isLine = false;
        Node[new_idx]->endpoints = {-1, -1};
    }
    else {
        //cout << "a = " << a << ", b = " << b << "\n";
        //cout << "A Line = " << Node[a]->endpoints.first << ", " << Node[a]->endpoints.second << "\n";
        //cout << "B Line = " << Node[b]->endpoints.first << ", " << Node[b]->endpoints.second << "\n";
        if(Node[a]->endpoints.first != original_a) {
            swap(Node[a]->endpoints.first, Node[a]->endpoints.second);
        }
        if(Node[b]->endpoints.first != original_b) {
            swap(Node[b]->endpoints.first, Node[b]->endpoints.second);
        }
        if(original_a == Node[a]->endpoints.first && original_b == Node[b]->endpoints.first) {
            Node[new_idx]->isLine = true;
            Node[new_idx]->endpoints = {Node[a]->endpoints.second, Node[b]->endpoints.second};
        }
        else {
            Node[new_idx]->isLine = false;
            Node[new_idx]->endpoints = {-1, -1};
        }
    }
}

bool cmp(array<int, 3> a, array<int, 3> b) {
    return a[2] < b[2];
}

void dfs(int node, int dep) {
    depth[node] = dep;
    for(int i = 0; i < g[node].size(); i++) {
        dfs(g[node][i], dep + 1);
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    auto begin = std::chrono::high_resolution_clock::now();
    for(int i = 0; i < 20; i++) {
        for(int j = 0; j < MAXN * 3; j++) {
            DP[i][j] = -1;
        }
    }
    for(int i = 0; i < M; i++) {
        edges[i] = {U[i], V[i], W[i]};
    }
    sort(edges.begin(), edges.begin() + M, cmp);
    int cur_new = N;
    for(int i = 0; i < MAXN * 3; i++) {
        Node[i] = new ufds(i);
    }
    for(int i = 0; i < M; i++) {
        //cout << Find(edges[i][0]) << " " << Find(edges[i][1]) << "\n"; 
        int x = Find(edges[i][0]), y = Find(edges[i][1]);
        //cout << "x = " << x << ", Node[x] is a line? " << Node[x]->isLine << "\n";
        if(x != y || Node[x]->isLine == true) {
            //cout << "Uniting edge: (" << edges[i][0] << ", " << edges[i][1] << ", " << edges[i][2] << ")\n";
            Unite(edges[i][0], edges[i][1], cur_new++, edges[i][2]);
        }
    }
    assert(cur_new <= MAXN * 3);
    for(int i = 1; i < 20; i++) {
        for(int j = 0; j < cur_new; j++) {
            if(DP[i - 1][j] != -1) {
                DP[i][j] = DP[i - 1][DP[i - 1][j]];
            }
            else {
                DP[i][j] = -1;
            }
        }
    }
    dfs(cur_new - 1, 0);
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << elapsed.count() * 1e-9 << "\n";
    if(elapsed.count() * 1e-9 > 2.0) {
        assert(false);
    }
}

bool Check(int val, int X, int Y) {
    for(int i = 19; i >= 0; i--) {
        if(DP[i][X] != -1 && Node[DP[i][X]]->value <= val) {
            X = DP[i][X];
        }
        if(DP[i][Y] != -1 && Node[DP[i][Y]]->value <= val) {
            Y = DP[i][Y];
        }
    }
    return (X == Y && Node[X]->isLine == false);
}

int lca(int X, int Y) {
    if(depth[X] < depth[Y]) {
        swap(X, Y);
    }
    int diff = depth[X] - depth[Y];
    for(int i = 19; i >= 0; i--) {
        if((1 << i) & diff) {
            X = DP[i][X];
        }
    }
    for(int i = 19; i >= 0; i--) {
        if(DP[i][X] != -1 && (DP[i][X] != DP[i][Y] || Node[DP[i][X]]->isLine)) {
            X = DP[i][X];
            Y = DP[i][Y];
        }
    }
    if(X != Y || Node[X]->isLine) {
        return -1;
    }
    return Node[X]->value;
}

int getMinimumFuelCapacity(int X, int Y) {
    return lca(X, Y);
}

Compilation message (stderr)

swap.cpp: In function 'void dfs(int, int)':
swap.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

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