제출 #551015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551015		hoanghq2004	자매 도시 (APIO20_swap)	C++14	53 / 100	261 ms	35720 KiB

swap

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define Submit
#ifdef Submit
#include "swap.h"

#endif // Submit

using namespace __gnu_pbds;
using namespace std;

const int N = 2e5 + 10;

int n;
int deg[N];
int root[N], ok[N];
vector <int> g[N];
int par[N][20];
int in[N], out[N], ti, ans[N];

int Find(int u) {
    return (u == root[u] ? u : root[u] = Find(root[u]));
}

int Union(int u, int v, int _) {
    ++n;
    root[n] = n;
    if ((u = Find(u)) == (v = Find(v))) {
        ok[n] = 1;
        root[u] = n;
        g[n].push_back(u);
    } else {
        ok[n] = ok[u] | ok[v] | _;
        root[u] = root[v] = n;
        g[n].push_back(u);
        g[n].push_back(v);
    }
    return n;
}

void dfs(int u) {
    in[u] = ++ti;
    for (auto v: g[u]) {
        par[v][0] = u;
        for (int i = 1; i < 20; ++i)
            par[v][i] = par[par[v][i - 1]][i - 1];
        dfs(v);
    }
    out[u] = ti;
}

int check(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

int LCA(int u, int v) {
    if (check(u, v)) return u;
    for (int i = 19; i >= 0; --i)
        if (par[u][i] && !check(par[u][i], v)) u = par[u][i];
    return par[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    vector <tuple <int, int, int> > e;
    for (int i = 1; i <= n; ++i) root[i] = i;
    for (int i = 0; i < M; ++i) {
        ++U[i], ++V[i];
        e.push_back({W[i], U[i], V[i]});
    }
    sort(e.begin(), e.end());
    for (int i = 0; i < e.size(); ++i) {
        auto [w, u, v] = e[i];
        ++deg[u], ++deg[v];
        int cur = Union(u, v, (deg[u] > 2 || deg[v] > 2));
        ans[cur] = w;
    }
    for (int i = n; i >= 1; --i)
        if (in[i] == 0) dfs(i);
}

int getMinimumFuelCapacity(int X, int Y) {
    ++X, ++Y;
    int w = LCA(X, Y);
    if (ok[w]) return ans[w];
    for (int i = 19; i >= 0; --i)
        if (par[w][i] && !ok[par[w][i]]) w = par[w][i];
    w = par[w][0];
    if (ok[w]) return ans[w];
    return -1;
}


#ifndef Submit

int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);

  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }

  return 0;
}

#endif // Submit

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

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < e.size(); ++i) {
      |                     ~~^~~~~~~~~~
swap.cpp:76:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |         auto [w, u, v] = e[i];
      |              ^

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