이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |