Submission #655572

#	Time	Username	Problem	Language	Result	Execution time	Memory
655572		Alexandruabcde	Swapping Cities (APIO20_swap)	C++14	100 / 100	221 ms	91596 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, pair <int, int> > PIII;

constexpr int NMAX = 1e5 + 2;
constexpr int MMAX = 2e5 + 2;

int WhatNode[NMAX+MMAX];
int Repr[NMAX+MMAX];
int Sz[NMAX+MMAX];
int Grad[NMAX];

int Reprezentant (int node) {
    if (node == Repr[node]) return node;

    return Repr[node] = Reprezentant(Repr[node]);
}

int Dad[NMAX+MMAX];
int Value[NMAX+MMAX];
bool Good[NMAX+MMAX];

vector <int> G[NMAX + MMAX];

void Unify (int x, int y, int new_nod, int lg) {
    int repr_x = Reprezentant(x);
    int repr_y = Reprezentant(y);

    ++ Grad[x];
    ++ Grad[y];

    if (repr_x == repr_y) {
        Dad[WhatNode[repr_x]] = new_nod;
        WhatNode[repr_x] = new_nod;
        Good[new_nod] = true;
        Value[new_nod] = lg;

        return;
    }

    if (Sz[repr_x] > Sz[repr_y]) swap(repr_x, repr_y);

    Repr[repr_x] = repr_y;
    Sz[repr_y] += Sz[repr_x];
    Dad[WhatNode[repr_y]] = new_nod;
    Dad[WhatNode[repr_x]] = new_nod;
    Value[new_nod] = lg;

    Good[new_nod] = false;
    Good[new_nod] = (Good[WhatNode[repr_x]]|Good[WhatNode[repr_y]]);
    if (Grad[x] >= 3 || Grad[y] >= 3) Good[new_nod] = true;
    WhatNode[repr_y] = new_nod;
}

int Best[NMAX + MMAX];
vector <int> Order;
int Level[NMAX + MMAX];

void Dfs (int Node) {
    Order.push_back(Node);
    if (Good[Node]) Best[Node] = Node;

    for (auto it : G[Node]) {
        Best[it] = Best[Node];
        Level[it] = Level[Node] + 1;

        Dfs(it);
        Order.push_back(Node);
    }
}

int Lg[2 * (NMAX+MMAX)];
int pos[NMAX+MMAX];
int RMQ[20][2 * (NMAX+MMAX)];

void Precompute (int Root) {
    Best[Root] = -1;
    Level[Root] = 0;

    Dfs(Root);

    Lg[1] = 0;
    for (int i = 2; i <= Order.size(); ++ i )
        Lg[i] = Lg[i/2] + 1;

    for (int i = 0; i <= Root; ++ i )
        pos[i] = -1;

    for (int i = 0; i < Order.size(); ++ i )
        if (pos[Order[i]] == -1) pos[Order[i]] = i;

    for (int i = 0; i < Order.size(); ++ i )
        RMQ[0][i] = Order[i];

    for (int lg = 1; lg <= Lg[Order.size()]; ++ lg ) {
        for (int i = 0; i + (1<<lg) < Order.size(); ++ i ) {
            if (Level[RMQ[lg-1][i]] < Level[RMQ[lg-1][i + (1<<(lg-1))]])
                RMQ[lg][i] = RMQ[lg-1][i];
            else RMQ[lg][i] = RMQ[lg-1][i + (1<<(lg-1))];
        }
    }
}

int LCA (int x, int y) {
    int st = min(pos[x], pos[y]);
    int dr = max(pos[x], pos[y]);

    int k = Lg[dr - st + 1];

    if (Level[RMQ[k][st]] < Level[RMQ[k][dr - (1<<k) + 1]])
        return RMQ[k][st];
    else return RMQ[k][dr - (1<<k) + 1];
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {

    vector <PIII> Edges;
    for (int i = 0; i < M; ++ i ) {
        Edges.push_back({W[i], {U[i], V[i]}});
    }

    sort(Edges.begin(), Edges.end());
    for (int i = 0; i < N; ++ i ) {
        WhatNode[i] = i;
        Repr[i] = i;
        Sz[i] = 1;
    }

    for (int i = 0; i < Edges.size(); ++ i )
        Unify(Edges[i].second.first, Edges[i].second.second, N + i, Edges[i].first);

    for (int i = 0; i < N + M - 1; ++ i )
        G[Dad[i]].push_back(i);

    Precompute(N + M - 1);
}

int getMinimumFuelCapacity(int X, int Y) {
    int Node = Best[LCA(X, Y)];

    if (Node == -1) return -1;

    return Value[Node];
}

Compilation message (stderr)

swap.cpp: In function 'void Precompute(int)':
swap.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 2; i <= Order.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~~
swap.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < Order.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~
swap.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for (int i = 0; i < Order.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~
swap.cpp:100:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int i = 0; i + (1<<lg) < Order.size(); ++ i ) {
      |                         ~~~~~~~~~~~~^~~~~~~~~~~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 0; i < Edges.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~~

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