Submission #977638

#TimeUsernameProblemLanguageResultExecution timeMemory
977638Ning07Swapping Cities (APIO20_swap)C++17
37 / 100
2095 ms13760 KiB
#include "swap.h" #include <vector> #include<bits/stdc++.h> using namespace std; #define L(i, j, k) for (int i = (j); i <= k; i++) #define R(i, j, k) for (int i = (j); i >= k; i--) struct dsu { vector<int> fa, sz; vector<bool> ok; dsu(int n) { fa.resize(n + 10); iota(fa.begin(), fa.end(), 0); sz.assign(n + 10, 1); ok.assign(n + 10, false); } int find(int x) { while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x; } bool merge(int x, int y) { int px = find(x), py = find(y); if (px == py) return false; if (sz[py] > sz[px]) swap(px, py); sz[px] += sz[py]; fa[py] = px; ok[px] = ok[px] || ok[py]; return true; } bool same(int x, int y) { int px = find(x), py = find(y); return px == py; } }; const int nax = 100050; int N, M; vector<pair<int, int>> G[nax]; vector<pair<int, pair<int, int>>> edges; void init(int _N, int _M, std::vector<int> _U, std::vector<int> _V, std::vector<int> _W) { N = _N; M = _M; L(i, 0, M - 1) edges.push_back(make_pair(_W[i], make_pair(_U[i], _V[i]))); sort(edges.begin(), edges.end()); } int getMinimumFuelCapacity(int X, int Y) { // in order to speed up, // we want to check connectivity, cycle, and whether the degree >= 3 dsu D(N); vector<int> deg(N); for (int i = 0; i < edges.size(); i++) { int w = edges[i].first; int u = edges[i].second.first, v = edges[i].second.second; if (D.same(u, v)) D.ok[D.find(u)] = true; // cycle is formed deg[u]++; deg[v]++; if (deg[u] >= 3) D.ok[D.find(u)] = true; // degree >= 3 if (deg[v] >= 3) D.ok[D.find(v)] = true; // degree >= 3 D.merge(u, v); // merge them if (D.same(X, Y) && D.ok[D.find(X)] == true) // if they are in the same component and its ok to swap them return w; } return -1; }

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for (int i = 0; i < edges.size(); 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...