# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
758401 | 2023-06-14T14:59:00 Z | yellowtoad | Swapping Cities (APIO20_swap) | C++17 | 163 ms | 76588 KB |
#include "swap.h" #include <iostream> #include <vector> #include <algorithm> #define f first #define s second using namespace std; int n, m, freq[100010], p[100010], id[100010], par[300010][20], depth[300010]; bool can[300010]; pair<int,pair<int,int>> ed[200010]; vector<int> edge[300010]; int dsu(int u) { if (p[u] == u) return u; return (p[u] = dsu(p[u])); } void dfs(int u, int d) { int v = par[u][0]; depth[u] = d; for (int i = 1; i <= 19; i++) { par[u][i] = par[v][i-1]; v = par[u][i]; } for (int i = 0; i < edge[u].size(); i++) dfs(edge[u][i],d+1); } int lca(int u, int v) { if (depth[v] < depth[u]) swap(u,v); int i = 19; while (depth[v] != depth[u]) { if (depth[par[v][i]] >= depth[u]) v = par[v][i]; i--; } if (v == u) return u; while (i >= 0) { if (par[v][i] != par[u][i]) { u = par[u][i]; v = par[v][i]; } i--; } return par[u][0]; } void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n = N; m = M; for (int i = 0; i < m; i++) ed[i] = {W[i],{U[i],V[i]}}; sort(ed,ed+m); for (int i = 0; i < n; i++) p[i] = id[i] = i; for (int i = 0; i < m; i++) { int u = ed[i].s.f, v = ed[i].s.s, w = ed[i].f; if (dsu(u) == dsu(v)) { par[id[dsu(u)]][0] = n+i; edge[n+i].push_back(id[dsu(u)]); id[dsu(u)] = n+i; freq[u]++; freq[v]++; can[n+i] = 1; } else { par[id[dsu(u)]][0] = n+i; par[id[dsu(v)]][0] = n+i; edge[n+i].push_back(id[dsu(u)]); edge[n+i].push_back(id[dsu(v)]); freq[u]++; freq[v]++; if ((freq[u] >= 3) || (freq[v] >= 3) || (can[id[dsu(u)]]) || (can[id[dsu(v)]])) can[n+i] = 1; p[dsu(v)] = p[dsu(u)]; id[dsu(u)] = n+i; } } dfs(n+m-1,1); can[0] = 1; } int getMinimumFuelCapacity(int U, int V) { int u = lca(U,V); if (can[u]) return ed[u-n].f; int i = 19; while (i >= 0) { if (!can[par[u][i]]) u = par[u][i]; i--; } if (!par[u][0]) return -1; return ed[par[u][0]-n].f; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7380 KB | Output is correct |
2 | Correct | 5 ms | 7352 KB | Output is correct |
3 | Correct | 4 ms | 7380 KB | Output is correct |
4 | Incorrect | 5 ms | 7508 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7380 KB | Output is correct |
2 | Correct | 5 ms | 7352 KB | Output is correct |
3 | Runtime error | 163 ms | 76588 KB | Execution killed with signal 11 |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7380 KB | Output is correct |
2 | Correct | 5 ms | 7352 KB | Output is correct |
3 | Correct | 4 ms | 7380 KB | Output is correct |
4 | Incorrect | 5 ms | 7508 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7380 KB | Output is correct |
2 | Correct | 5 ms | 7352 KB | Output is correct |
3 | Correct | 4 ms | 7380 KB | Output is correct |
4 | Incorrect | 5 ms | 7508 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7380 KB | Output is correct |
2 | Correct | 5 ms | 7352 KB | Output is correct |
3 | Correct | 4 ms | 7380 KB | Output is correct |
4 | Incorrect | 5 ms | 7508 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7380 KB | Output is correct |
2 | Correct | 5 ms | 7352 KB | Output is correct |
3 | Correct | 4 ms | 7380 KB | Output is correct |
4 | Incorrect | 5 ms | 7508 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |