oj.uz

Submission #571286

# Submission time Handle Problem Language Result Execution time Memory
571286 2022-06-01T16:13:12 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 408 ms 76744 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];
vector <bool> good (maxn, 0);
vector <int> cmp[maxn];
vector <int> depth (maxn);
int dg[maxn];
int up[maxn][lg];
 
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);
  }
}
 
bool propagate (int u) {
  for (int v: ad[u]) {
    good[u]= good[u] | propagate(v);
  }
  return good[u];
}
 
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++){
    eg.push_back({u[i], v[i], w[i]});
  }
  sort(eg.begin(), eg.end(), comp);
  for (auto &[u,v,cost]: eg) {
    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 = maxn - 1; i >= 0; i--){
    if (!cmp[i].empty()) {
      propagate(i);
      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 32 ms 61384 KB Output is correct
2 Correct 31 ms 61324 KB Output is correct
3 Correct 30 ms 61396 KB Output is correct
4 Correct 28 ms 61436 KB Output is correct
5 Correct 28 ms 61452 KB Output is correct
6 Correct 35 ms 61392 KB Output is correct
7 Correct 36 ms 61456 KB Output is correct
8 Correct 33 ms 61480 KB Output is correct
9 Correct 131 ms 67196 KB Output is correct
10 Correct 153 ms 68544 KB Output is correct
11 Correct 140 ms 68424 KB Output is correct
12 Correct 144 ms 68744 KB Output is correct
13 Correct 156 ms 71936 KB Output is correct
14 Correct 151 ms 67364 KB Output is correct
15 Correct 294 ms 70136 KB Output is correct
16 Correct 305 ms 69964 KB Output is correct
17 Correct 280 ms 70432 KB Output is correct
18 Correct 390 ms 73560 KB Output is correct
19 Correct 139 ms 65912 KB Output is correct
20 Correct 293 ms 70368 KB Output is correct
21 Correct 296 ms 70420 KB Output is correct
22 Correct 294 ms 70868 KB Output is correct
23 Correct 408 ms 73996 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61384 KB Output is correct
2 Correct 31 ms 61324 KB Output is correct
3 Correct 358 ms 76196 KB Output is correct
4 Correct 377 ms 76716 KB Output is correct
5 Correct 370 ms 76652 KB Output is correct
6 Correct 319 ms 76648 KB Output is correct
7 Correct 359 ms 76744 KB Output is correct
8 Correct 347 ms 76248 KB Output is correct
9 Correct 320 ms 76520 KB Output is correct
10 Correct 384 ms 76148 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61384 KB Output is correct
2 Correct 31 ms 61324 KB Output is correct
3 Correct 30 ms 61396 KB Output is correct
4 Correct 28 ms 61436 KB Output is correct
5 Correct 28 ms 61452 KB Output is correct
6 Correct 35 ms 61392 KB Output is correct
7 Correct 36 ms 61456 KB Output is correct
8 Correct 33 ms 61480 KB Output is correct
9 Correct 30 ms 61396 KB Output is correct
10 Incorrect 28 ms 61472 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 61396 KB Output is correct
2 Correct 32 ms 61384 KB Output is correct
3 Correct 31 ms 61324 KB Output is correct
4 Correct 30 ms 61396 KB Output is correct
5 Correct 28 ms 61436 KB Output is correct
6 Correct 28 ms 61452 KB Output is correct
7 Correct 35 ms 61392 KB Output is correct
8 Correct 36 ms 61456 KB Output is correct
9 Correct 33 ms 61480 KB Output is correct
10 Correct 131 ms 67196 KB Output is correct
11 Correct 153 ms 68544 KB Output is correct
12 Correct 140 ms 68424 KB Output is correct
13 Correct 144 ms 68744 KB Output is correct
14 Correct 156 ms 71936 KB Output is correct
15 Incorrect 28 ms 61472 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61384 KB Output is correct
2 Correct 31 ms 61324 KB Output is correct
3 Correct 30 ms 61396 KB Output is correct
4 Correct 28 ms 61436 KB Output is correct
5 Correct 28 ms 61452 KB Output is correct
6 Correct 35 ms 61392 KB Output is correct
7 Correct 36 ms 61456 KB Output is correct
8 Correct 33 ms 61480 KB Output is correct
9 Correct 131 ms 67196 KB Output is correct
10 Correct 153 ms 68544 KB Output is correct
11 Correct 140 ms 68424 KB Output is correct
12 Correct 144 ms 68744 KB Output is correct
13 Correct 156 ms 71936 KB Output is correct
14 Correct 151 ms 67364 KB Output is correct
15 Correct 294 ms 70136 KB Output is correct
16 Correct 305 ms 69964 KB Output is correct
17 Correct 280 ms 70432 KB Output is correct
18 Correct 390 ms 73560 KB Output is correct
19 Correct 358 ms 76196 KB Output is correct
20 Correct 377 ms 76716 KB Output is correct
21 Correct 370 ms 76652 KB Output is correct
22 Correct 319 ms 76648 KB Output is correct
23 Correct 359 ms 76744 KB Output is correct
24 Correct 347 ms 76248 KB Output is correct
25 Correct 320 ms 76520 KB Output is correct
26 Correct 384 ms 76148 KB Output is correct
27 Incorrect 28 ms 61472 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 61396 KB Output is correct
2 Correct 32 ms 61384 KB Output is correct
3 Correct 31 ms 61324 KB Output is correct
4 Correct 30 ms 61396 KB Output is correct
5 Correct 28 ms 61436 KB Output is correct
6 Correct 28 ms 61452 KB Output is correct
7 Correct 35 ms 61392 KB Output is correct
8 Correct 36 ms 61456 KB Output is correct
9 Correct 33 ms 61480 KB Output is correct
10 Correct 131 ms 67196 KB Output is correct
11 Correct 153 ms 68544 KB Output is correct
12 Correct 140 ms 68424 KB Output is correct
13 Correct 144 ms 68744 KB Output is correct
14 Correct 156 ms 71936 KB Output is correct
15 Correct 151 ms 67364 KB Output is correct
16 Correct 294 ms 70136 KB Output is correct
17 Correct 305 ms 69964 KB Output is correct
18 Correct 280 ms 70432 KB Output is correct
19 Correct 390 ms 73560 KB Output is correct
20 Correct 358 ms 76196 KB Output is correct
21 Correct 377 ms 76716 KB Output is correct
22 Correct 370 ms 76652 KB Output is correct
23 Correct 319 ms 76648 KB Output is correct
24 Correct 359 ms 76744 KB Output is correct
25 Correct 347 ms 76248 KB Output is correct
26 Correct 320 ms 76520 KB Output is correct
27 Correct 384 ms 76148 KB Output is correct
28 Incorrect 28 ms 61472 KB Output isn't correct
29 Halted 0 ms 0 KB -