Submission #401051

#TimeUsernameProblemLanguageResultExecution timeMemory
401051salehSwapping Cities (APIO20_swap)C++17
0 / 100
2081 ms27220 KiB
#include "swap.h" #include <bits/stdc++.h> #define sd second #define ft first using namespace std; typedef pair<int, int> pii; const int MAXN = 100 * 1000 + 23, MAXM = 200 * 1000 + 23; int n, m, a[MAXM]; int par[MAXN], ot[MAXN], deg[MAXN], comp[MAXN]; vector<pii> cn[MAXN]; vector<int> r[MAXN]; int get(int x) { return (par[x] >= 0? par[x] = get(par[x]): x); } bool mrg(int x, int y, int w) { int u = get(x), v = get(y); if (u == v) return true; deg[x]++, deg[y]++; if (par[u] < par[v]) swap(u, v); for (auto i : r[u]) { r[v].push_back(i); comp[i] = comp[v]; cn[i].push_back({comp[v], w}); } par[v] += par[u]; par[u] = v; if (deg[x] > 2 || deg[y] > 2) return true; return ((ot[comp[u]] != -1) || (ot[comp[v]] != -1)); } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N; m = M; memset(ot, -1, sizeof ot); memset(par, -1, sizeof par); iota(comp, comp + n, 0); for (int i = 0; i < n; i++) { cn[i].push_back({i, -1}); r[i].push_back(i); } iota(a, a + m, 0); sort(a, a + m, [W](int x, int y) { return W[x] < W[y]; }); for (int o = 0; o < m; o++) { int i = a[o]; if (mrg(U[i], V[i], W[i])) if (ot[comp[U[i]]] == -1) ot[comp[U[i]]] = W[i]; } } int getMinimumFuelCapacity(int x, int y) { if (x == y) return 0;// int jav = -1, jabe = -1; for (auto i : cn[x]) { int ans = -1; for (auto j : cn[y]) if (i.ft == j.ft) { ans = max(i.sd, j.sd); break; } if (~ans) if (jav == -1 || jav > ans) { jav = ans; jabe = i.ft; } } int ind = 0; while (cn[x][ind].ft != jabe) ind++; while (ind < cn[x].size() && ot[cn[x][ind].ft] == -1) ind++; if (ind == cn[x].size()) return -1; return max(jav, ot[cn[x][ind].ft]); } /* int main() { init(5, 6, {0,0,1,1,1,2}, {1,2,2,3,4,3}, {4,4,1,2,10,3}); cout << getMinimumFuelCapacity(1, 2) << endl << getMinimumFuelCapacity(2, 4) << endl << getMinimumFuelCapacity(0, 1) << endl; return 0; }*/

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:86:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while (ind < cn[x].size() && ot[cn[x][ind].ft] == -1) ind++;
      |         ~~~~^~~~~~~~~~~~~~
swap.cpp:87:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  if (ind == cn[x].size()) return -1;
      |      ~~~~^~~~~~~~~~~~~~~
#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...