oj.uz

Submission #571280

# Submission time Handle Problem Language Result Execution time Memory
571280 2022-06-01T16:01:42 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 400 ms 80000 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 2e5 + 1;
// int extra = 9;
const int lg = 25;
vector <int> ad [maxn];
int deg[maxn];
int dad [maxn];
int val [maxn];
bitset <maxn> good;
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] || !good[up[x][i]]) {
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}
 
 
int get_dad (int x) {
  return dad[x] = (dad[x] == x ? x: get_dad(dad[x]));
}
 
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;
  good [maxn - 1] = 1;
  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);
    deg[u]++;
    deg[v]++;
    val[++extra] = cost;
    dad[p1] = extra;
    dad[p2] = extra;
    cmp[extra].push_back(p1);
    if (p1 != p2) cmp[extra].push_back(p2);
    if (p1 == p2 || deg[u] >= 3 || deg[v] >= 3) {
      good[extra] = 1;
    }
  
  }
  // for (int i = 0; i <= 16; i++) {
  //   cout << good[i] << " " << val[i] << " ";
  //   cout << i << ": ";
  //   for (int j: cmp[i]) {
  //     cout << j << " ";
  //   }
  //   cout << '\n';
  // }
  for (int i = maxn - 1; i >= 0; i--){
    if (!cmp[i].empty()) {
      dfs(i);
      break;
    }
  }
 
}
 
int getMinimumFuelCapacity(int x, int y) {
  int k = lca(x,y);
  if (!good[k] || k == maxn - 1) return -1;
  return val[k];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61260 KB Output is correct
2 Correct 29 ms 61280 KB Output is correct
3 Correct 28 ms 61384 KB Output is correct
4 Correct 28 ms 61396 KB Output is correct
5 Correct 33 ms 61352 KB Output is correct
6 Correct 31 ms 61384 KB Output is correct
7 Correct 40 ms 61376 KB Output is correct
8 Correct 32 ms 61380 KB Output is correct
9 Correct 120 ms 67412 KB Output is correct
10 Correct 146 ms 68884 KB Output is correct
11 Correct 143 ms 68756 KB Output is correct
12 Correct 148 ms 69188 KB Output is correct
13 Correct 148 ms 72240 KB Output is correct
14 Correct 132 ms 67552 KB Output is correct
15 Correct 276 ms 70416 KB Output is correct
16 Correct 264 ms 70276 KB Output is correct
17 Correct 290 ms 70720 KB Output is correct
18 Correct 400 ms 73804 KB Output is correct
19 Correct 130 ms 65896 KB Output is correct
20 Correct 269 ms 70716 KB Output is correct
21 Correct 282 ms 70832 KB Output is correct
22 Correct 284 ms 71192 KB Output is correct
23 Correct 389 ms 74368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61260 KB Output is correct
2 Correct 29 ms 61280 KB Output is correct
3 Correct 322 ms 76632 KB Output is correct
4 Correct 357 ms 80000 KB Output is correct
5 Correct 370 ms 79784 KB Output is correct
6 Correct 355 ms 79792 KB Output is correct
7 Correct 370 ms 79960 KB Output is correct
8 Correct 356 ms 79400 KB Output is correct
9 Correct 364 ms 79660 KB Output is correct
10 Correct 324 ms 79236 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61260 KB Output is correct
2 Correct 29 ms 61280 KB Output is correct
3 Correct 28 ms 61384 KB Output is correct
4 Correct 28 ms 61396 KB Output is correct
5 Correct 33 ms 61352 KB Output is correct
6 Correct 31 ms 61384 KB Output is correct
7 Correct 40 ms 61376 KB Output is correct
8 Correct 32 ms 61380 KB Output is correct
9 Correct 29 ms 61296 KB Output is correct
10 Incorrect 29 ms 61432 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61296 KB Output is correct
2 Correct 28 ms 61260 KB Output is correct
3 Correct 29 ms 61280 KB Output is correct
4 Correct 28 ms 61384 KB Output is correct
5 Correct 28 ms 61396 KB Output is correct
6 Correct 33 ms 61352 KB Output is correct
7 Correct 31 ms 61384 KB Output is correct
8 Correct 40 ms 61376 KB Output is correct
9 Correct 32 ms 61380 KB Output is correct
10 Correct 120 ms 67412 KB Output is correct
11 Correct 146 ms 68884 KB Output is correct
12 Correct 143 ms 68756 KB Output is correct
13 Correct 148 ms 69188 KB Output is correct
14 Correct 148 ms 72240 KB Output is correct
15 Incorrect 29 ms 61432 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 61260 KB Output is correct
2 Correct 29 ms 61280 KB Output is correct
3 Correct 28 ms 61384 KB Output is correct
4 Correct 28 ms 61396 KB Output is correct
5 Correct 33 ms 61352 KB Output is correct
6 Correct 31 ms 61384 KB Output is correct
7 Correct 40 ms 61376 KB Output is correct
8 Correct 32 ms 61380 KB Output is correct
9 Correct 120 ms 67412 KB Output is correct
10 Correct 146 ms 68884 KB Output is correct
11 Correct 143 ms 68756 KB Output is correct
12 Correct 148 ms 69188 KB Output is correct
13 Correct 148 ms 72240 KB Output is correct
14 Correct 132 ms 67552 KB Output is correct
15 Correct 276 ms 70416 KB Output is correct
16 Correct 264 ms 70276 KB Output is correct
17 Correct 290 ms 70720 KB Output is correct
18 Correct 400 ms 73804 KB Output is correct
19 Correct 322 ms 76632 KB Output is correct
20 Correct 357 ms 80000 KB Output is correct
21 Correct 370 ms 79784 KB Output is correct
22 Correct 355 ms 79792 KB Output is correct
23 Correct 370 ms 79960 KB Output is correct
24 Correct 356 ms 79400 KB Output is correct
25 Correct 364 ms 79660 KB Output is correct
26 Correct 324 ms 79236 KB Output is correct
27 Incorrect 29 ms 61432 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61296 KB Output is correct
2 Correct 28 ms 61260 KB Output is correct
3 Correct 29 ms 61280 KB Output is correct
4 Correct 28 ms 61384 KB Output is correct
5 Correct 28 ms 61396 KB Output is correct
6 Correct 33 ms 61352 KB Output is correct
7 Correct 31 ms 61384 KB Output is correct
8 Correct 40 ms 61376 KB Output is correct
9 Correct 32 ms 61380 KB Output is correct
10 Correct 120 ms 67412 KB Output is correct
11 Correct 146 ms 68884 KB Output is correct
12 Correct 143 ms 68756 KB Output is correct
13 Correct 148 ms 69188 KB Output is correct
14 Correct 148 ms 72240 KB Output is correct
15 Correct 132 ms 67552 KB Output is correct
16 Correct 276 ms 70416 KB Output is correct
17 Correct 264 ms 70276 KB Output is correct
18 Correct 290 ms 70720 KB Output is correct
19 Correct 400 ms 73804 KB Output is correct
20 Correct 322 ms 76632 KB Output is correct
21 Correct 357 ms 80000 KB Output is correct
22 Correct 370 ms 79784 KB Output is correct
23 Correct 355 ms 79792 KB Output is correct
24 Correct 370 ms 79960 KB Output is correct
25 Correct 356 ms 79400 KB Output is correct
26 Correct 364 ms 79660 KB Output is correct
27 Correct 324 ms 79236 KB Output is correct
28 Incorrect 29 ms 61432 KB Output isn't correct
29 Halted 0 ms 0 KB -