oj.uz

Submission #571188

# Submission time Handle Problem Language Result Execution time Memory
571188 2022-06-01T12:24:03 Z Vanilla Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 68888 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 2e5 + 1;
const int lg = 25;
vector <int> ad [maxn];
int deg[maxn];
int dad [maxn];
int val [maxn];
vector <bool> line (maxn, 1);
vector <int> cmp[maxn];
vector <int> depth (maxn);
int dg[maxn];
int up[maxn][lg];
bool bad1 = 1, bad2 = 1;
 
void dfs (int u) {
    for (auto v: cmp[u]) {
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        for (int i = 1; i < lg; i++){
            up[v][i] = up[up[v][i-1]][i-1];
        }
        dfs(v);
    }
}
 
int lca (int x, int y) {
    if (depth[x] < depth[y]) {
        swap(x, y);
    }
    int k = depth[x] - depth[y];
    for (int i = 0; i < lg; i++){
        if (k & (1 << i)) {
            x = up[x][i];
        }
    }
    if (x == y) return x;
    for (int i = lg - 1; i >= 0; i--) {
        if (up[x][i] != up[y][i]) {
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}
 
 
int get_dad (int x) {
  return (dad[x] == x ? x: get_dad(dad[x]));
}
 
void merge (int a, int b) {
  a = get_dad(a);
  b = get_dad(b);
  if (a == b) return;
  if (!line[a]) line[b] = 0;
  dad[a] = b;
  cmp[b].push_back(a);
}
 
void find (int u, vector <int> &nodes) {
  nodes.push_back(u);
  for (int v: cmp[u]) {
    find(v, nodes);
  }
}
 
 
struct edg {
  int x,y,cost;
};
 
bool comp (edg &a, edg &b) {
  return a.cost < b.cost;
}
 
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
  vector <edg> eg;
  for (int i = 0; i < maxn; i++){
    dad[i] = i;
    for (int j = 0; j < lg; j++){
      up[i][j] = maxn - 1;
    }
  }
  for (int i = 0; i < m; i++){
    dg[u[i]]++;
    dg[v[i]]++;
    eg.push_back({u[i], v[i], w[i]});
  }
  for (int i = 0; i < n; i++){
    if (dg[i] > 2) bad1 = 0;
    if (dg[i] != 2) bad2 = 0;
  }
  sort(eg.begin(), eg.end(), comp);
  for (auto &[u,v,cost]: eg) {
    // if (u == 1 && v == 4) break;
    int p1 = get_dad(u);
    int p2 = get_dad(v);
    // cout << u << " " << v << " " << p1 << " " << p2 << " ";
    if (p1 == p2) { 
      if (line[p1]) {
        vector <int> nodes;
        find(p1, nodes);
        int node = ++extra;
        for (int i: nodes) {
          dad[i] = node;
          cmp[node].push_back(i);
        }
        line[p1] = 0;
        val[node] = cost;
      }
    }
    else {
      deg[u]++;
      deg[v]++;
      if (deg[u] >= 3 || deg[v] >= 3) {
        int node = ++extra;
        line[node] = 0;
        merge(p1, node);
        merge(p2, node);
        val[node] = cost;
      }
      else merge(u,v);
    }
  }
  // for (int i = 0; i < 15; i++){
  //   cout << i << " " << val[i] << "\n";
  // }
  // for (int i = 0; i < 15; i++){
  //   cout << i << ": ";
  //   for (int j: cmp[i]) {
  //     cout << j << " ";
  //   }
  //   cout << "\n";
  // }
  // for (int i = 0; i < 15; i++){
  //   cout << i << " " << dad[i] << "\n";
  // }
  for (int i = maxn - 1; i >= 0; i--){
    if (cmp[i].size()) {
      dfs(i);
      break;
    }
  }
 
}
 
int getMinimumFuelCapacity(int x, int y) {
  if (bad1 || bad2) return -1;
  return val[lca(x,y)];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61396 KB Output is correct
2 Correct 32 ms 61348 KB Output is correct
3 Correct 29 ms 61340 KB Output is correct
4 Correct 29 ms 61356 KB Output is correct
5 Correct 29 ms 61436 KB Output is correct
6 Correct 28 ms 61452 KB Output is correct
7 Correct 29 ms 61396 KB Output is correct
8 Correct 29 ms 61400 KB Output is correct
9 Correct 69 ms 66060 KB Output is correct
10 Correct 78 ms 67016 KB Output is correct
11 Correct 71 ms 67008 KB Output is correct
12 Correct 82 ms 67368 KB Output is correct
13 Correct 97 ms 68452 KB Output is correct
14 Correct 71 ms 66192 KB Output is correct
15 Correct 121 ms 68708 KB Output is correct
16 Correct 117 ms 68468 KB Output is correct
17 Correct 158 ms 68860 KB Output is correct
18 Correct 125 ms 68888 KB Output is correct
19 Incorrect 97 ms 64700 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61396 KB Output is correct
2 Correct 32 ms 61348 KB Output is correct
3 Execution timed out 2077 ms 68716 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61396 KB Output is correct
2 Correct 32 ms 61348 KB Output is correct
3 Correct 29 ms 61340 KB Output is correct
4 Correct 29 ms 61356 KB Output is correct
5 Correct 29 ms 61436 KB Output is correct
6 Correct 28 ms 61452 KB Output is correct
7 Correct 29 ms 61396 KB Output is correct
8 Correct 29 ms 61400 KB Output is correct
9 Correct 29 ms 61396 KB Output is correct
10 Correct 33 ms 61424 KB Output is correct
11 Incorrect 30 ms 61476 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61396 KB Output is correct
2 Correct 29 ms 61396 KB Output is correct
3 Correct 32 ms 61348 KB Output is correct
4 Correct 29 ms 61340 KB Output is correct
5 Correct 29 ms 61356 KB Output is correct
6 Correct 29 ms 61436 KB Output is correct
7 Correct 28 ms 61452 KB Output is correct
8 Correct 29 ms 61396 KB Output is correct
9 Correct 29 ms 61400 KB Output is correct
10 Correct 69 ms 66060 KB Output is correct
11 Correct 78 ms 67016 KB Output is correct
12 Correct 71 ms 67008 KB Output is correct
13 Correct 82 ms 67368 KB Output is correct
14 Correct 97 ms 68452 KB Output is correct
15 Correct 33 ms 61424 KB Output is correct
16 Incorrect 30 ms 61476 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61396 KB Output is correct
2 Correct 32 ms 61348 KB Output is correct
3 Correct 29 ms 61340 KB Output is correct
4 Correct 29 ms 61356 KB Output is correct
5 Correct 29 ms 61436 KB Output is correct
6 Correct 28 ms 61452 KB Output is correct
7 Correct 29 ms 61396 KB Output is correct
8 Correct 29 ms 61400 KB Output is correct
9 Correct 69 ms 66060 KB Output is correct
10 Correct 78 ms 67016 KB Output is correct
11 Correct 71 ms 67008 KB Output is correct
12 Correct 82 ms 67368 KB Output is correct
13 Correct 97 ms 68452 KB Output is correct
14 Correct 71 ms 66192 KB Output is correct
15 Correct 121 ms 68708 KB Output is correct
16 Correct 117 ms 68468 KB Output is correct
17 Correct 158 ms 68860 KB Output is correct
18 Correct 125 ms 68888 KB Output is correct
19 Execution timed out 2077 ms 68716 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61396 KB Output is correct
2 Correct 29 ms 61396 KB Output is correct
3 Correct 32 ms 61348 KB Output is correct
4 Correct 29 ms 61340 KB Output is correct
5 Correct 29 ms 61356 KB Output is correct
6 Correct 29 ms 61436 KB Output is correct
7 Correct 28 ms 61452 KB Output is correct
8 Correct 29 ms 61396 KB Output is correct
9 Correct 29 ms 61400 KB Output is correct
10 Correct 69 ms 66060 KB Output is correct
11 Correct 78 ms 67016 KB Output is correct
12 Correct 71 ms 67008 KB Output is correct
13 Correct 82 ms 67368 KB Output is correct
14 Correct 97 ms 68452 KB Output is correct
15 Correct 71 ms 66192 KB Output is correct
16 Correct 121 ms 68708 KB Output is correct
17 Correct 117 ms 68468 KB Output is correct
18 Correct 158 ms 68860 KB Output is correct
19 Correct 125 ms 68888 KB Output is correct
20 Execution timed out 2077 ms 68716 KB Time limit exceeded
21 Halted 0 ms 0 KB -