제출 #875315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875315		sleepntsheep	자매 도시 (APIO20_swap)	C++17	17 / 100	68 ms	33732 KiB

swap

#include "swap.h"
#include <iostream>
#include <tuple>
#include <algorithm> 
#include <vector>

using namespace std;
#define N 100000
#define M 200000

vector<int> g[N];
int p[N+M], P[N+M], J[N+M], D[N+M], d[N+M], f[N+M], l, V[N+M], W[N+M];

int fnd(int x) { return p[x] == x ? x : p[x] = fnd(p[x]); }

void link(int w, int u, int v)
{
    int ru = fnd(u), rv = fnd(v), sw = f[ru] | f[rv];
    if (ru == rv) { if (f[ru]) return; f[ru] = 1; W[ru] = w; return; }
    if (++d[u] >= 3 || ++d[v] >= 3) sw = 1;
    u = ru, v = rv;
    p[u] = p[v] = l; W[l] = w;
    g[l].push_back(u), g[l].push_back(v);
    f[l++] = sw;
}

void dfs(int u)
{
    V[u] = 1;
    for (auto v : g[u]) if (!V[v])
    {
        P[v] = u; D[v] = D[u] + 1;
        J[v] = (D[u] - D[J[u]] == D[J[u]] - D[J[J[u]]] ? J[J[u]] : u);
        dfs(v);
    }
}

int lca(int u, int v)
{
    if (D[u] < D[v]) return lca(v, u);
    if (fnd(u) != fnd(v)) return -1;
    while (D[u] > D[v])
    {
        if (D[J[u]] >= D[v]) u = J[u];
        else u = P[u];
    }
    while (u != v)
    {
        if (J[u] == J[v]) u = P[u], v = P[v];
        else u = J[u], v = J[v];
    }
    return u;
}

int lowest_switchable(int u)
{
    while (!f[u] && u != P[u])
        if (f[J[u]]) u = P[u];
        else u = J[u];
    return u;
}

void init(int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> w)
{
    vector<tuple<int, int, int>> e;
    l = n;
    for (int i = 0; i < u.size(); ++i) e.emplace_back(w[i], u[i], v[i]); 
    sort(e.begin(), e.end());
    for (int i = 0; i < n + m; ++i) p[i] = i;

    for (auto &[w, u, v] : e) link(w, u, v);
    for (int i = l; --i; ) if (!V[i])
        dfs(P[i] = J[i] = i);
}

int getMinimumFuelCapacity(int x, int y)
{
    int a = lca(x, y);
    if (a == -1) return -1;
    int b = lowest_switchable(a);
    if (!f[b]) return -1;
    return W[b];
}

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < u.size(); ++i) e.emplace_back(w[i], u[i], v[i]);
      |                     ~~^~~~~~~~~~

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