제출 #551015

#제출 시각아이디문제언어결과실행 시간메모리
551015hoanghq2004자매 도시 (APIO20_swap)C++14
53 / 100
261 ms35720 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...