Submission #555011

#	Time	Username	Problem	Language	Result	Execution time	Memory
555011		Zhora_004	Swapping Cities (APIO20_swap)	C++17	100 / 100	292 ms	13596 KiB

swap

#include "swap.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
#include <fstream>
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const int inf = 1e9;

struct Edge {
	int w, u, v;
};

bool comp(Edge& e1, Edge& e2)
{
	return e1.w < e2.w;
}

int n, m, q, x, y;
vector<int> a, b, c, par, rnk, start, finish, neww, noline;
vector<Edge> edges;

int find_par(int u)
{
	if (u == par[u]) return u;
	return find_par(par[u]);
}

void union_sets(int p1, int p2, int u, int v, int w)
{
    if (rnk[p1] < rnk[p2]) swap(p1, p2);
    par[p2] = p1;
    if (rnk[p1] == rnk[p2]) rnk[p1]++;
    neww[p2] = w;
    if (noline[p1] == noline[p2] && noline[p1] == 2 * inf)
    {
        if (finish[p1] == u && start[p2] == v) finish[p1] = finish[p2];
        else if (finish[p1] == u && finish[p2] == v) finish[p1] = start[p2];
        else if (start[p1] == u && start[p2] == v) start[p1] = finish[p2];
        else if (start[p1] == u && finish[p2] == v) start[p1] = start[p2];

        else if (finish[p1] == v && start[p2] == u) finish[p1] = finish[p2];
        else if (finish[p1] == v && finish[p2] == u) finish[p1] = start[p2];
        else if (start[p1] == v && start[p2] == u) start[p1] = finish[p2];
        else if (start[p1] == v && finish[p2] == u) start[p1] = start[p2];
        else
        {
            start[p1] = finish[p1] = -1;
            noline[p1] = w;
        }
    }
    else
    {
        start[p1] = finish[p1] = -1;
        noline[p1] = min(noline[p1], w);
    }
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	n = N;
	m = M;
	a = U;
	b = V;
	c = W;
    for (int i = 0; i < m; i++) edges.push_back({ c[i], a[i], b[i] });
    sort(edges.begin(), edges.end(), comp);
    par = rnk = start = finish = neww = vector<int>(n);
    noline = vector<int>(n, 2 * inf);
    iota(par.begin(), par.end(), 0);
    iota(start.begin(), start.end(), 0);
    iota(finish.begin(), finish.end(), 0);
    for (int i = 0; i < m; i++)
    {
        int w = edges[i].w, u = edges[i].u, v = edges[i].v;
        int p1 = find_par(u), p2 = find_par(v);
        if (p1 == p2)
        {
            start[p1] = finish[p1] = -1;
            noline[p1] = min(noline[p1], w);
        }
        else union_sets(p1, p2, u, v, w);
    }
}

int find_par1(int u, int& mid)
{
    if (u == par[u] || neww[u] > mid) return u;
    return find_par1(par[u], mid);
}

bool ok(int mid, int u, int v)
{
    int p1 = find_par1(u, mid), p2 = find_par1(v, mid);
    if (p1 != p2 || noline[p1] > mid) return 0;
    return 1;
}

int getMinimumFuelCapacity(int X, int Y) {
	x = X;
	y = Y;
    int l = 0, r = inf + 1;
    while (l + 1 < r)
    {
        int mid = (l + r) >> 1;
        if (ok(mid, x, y)) r = mid;
        else l = mid;
    }
    if (r == inf + 1) r = -1;
    return r;
}

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