oj.uz

Submission #571289

# Submission time Handle Problem Language Result Execution time Memory
571289 2022-06-01T16:17:31 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 447 ms 76756 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 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 && good[x]) 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 27 ms 61396 KB Output is correct
2 Correct 28 ms 61316 KB Output is correct
3 Correct 28 ms 61348 KB Output is correct
4 Correct 32 ms 61432 KB Output is correct
5 Correct 29 ms 61400 KB Output is correct
6 Correct 30 ms 61372 KB Output is correct
7 Correct 33 ms 61432 KB Output is correct
8 Correct 33 ms 61520 KB Output is correct
9 Correct 139 ms 67204 KB Output is correct
10 Correct 142 ms 68500 KB Output is correct
11 Correct 148 ms 68436 KB Output is correct
12 Correct 174 ms 68800 KB Output is correct
13 Correct 134 ms 71876 KB Output is correct
14 Correct 142 ms 67332 KB Output is correct
15 Correct 312 ms 70268 KB Output is correct
16 Correct 273 ms 69964 KB Output is correct
17 Correct 360 ms 70388 KB Output is correct
18 Correct 447 ms 73540 KB Output is correct
19 Correct 153 ms 65796 KB Output is correct
20 Correct 283 ms 70380 KB Output is correct
21 Correct 333 ms 70544 KB Output is correct
22 Correct 315 ms 70852 KB Output is correct
23 Correct 427 ms 73892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 61396 KB Output is correct
2 Correct 28 ms 61316 KB Output is correct
3 Correct 345 ms 76172 KB Output is correct
4 Correct 352 ms 76700 KB Output is correct
5 Correct 403 ms 76700 KB Output is correct
6 Correct 333 ms 76552 KB Output is correct
7 Correct 364 ms 76756 KB Output is correct
8 Correct 366 ms 76152 KB Output is correct
9 Correct 389 ms 76612 KB Output is correct
10 Correct 316 ms 76136 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 61396 KB Output is correct
2 Correct 28 ms 61316 KB Output is correct
3 Correct 28 ms 61348 KB Output is correct
4 Correct 32 ms 61432 KB Output is correct
5 Correct 29 ms 61400 KB Output is correct
6 Correct 30 ms 61372 KB Output is correct
7 Correct 33 ms 61432 KB Output is correct
8 Correct 33 ms 61520 KB Output is correct
9 Correct 36 ms 61504 KB Output is correct
10 Incorrect 32 ms 61424 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 61504 KB Output is correct
2 Correct 27 ms 61396 KB Output is correct
3 Correct 28 ms 61316 KB Output is correct
4 Correct 28 ms 61348 KB Output is correct
5 Correct 32 ms 61432 KB Output is correct
6 Correct 29 ms 61400 KB Output is correct
7 Correct 30 ms 61372 KB Output is correct
8 Correct 33 ms 61432 KB Output is correct
9 Correct 33 ms 61520 KB Output is correct
10 Correct 139 ms 67204 KB Output is correct
11 Correct 142 ms 68500 KB Output is correct
12 Correct 148 ms 68436 KB Output is correct
13 Correct 174 ms 68800 KB Output is correct
14 Correct 134 ms 71876 KB Output is correct
15 Incorrect 32 ms 61424 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 61396 KB Output is correct
2 Correct 28 ms 61316 KB Output is correct
3 Correct 28 ms 61348 KB Output is correct
4 Correct 32 ms 61432 KB Output is correct
5 Correct 29 ms 61400 KB Output is correct
6 Correct 30 ms 61372 KB Output is correct
7 Correct 33 ms 61432 KB Output is correct
8 Correct 33 ms 61520 KB Output is correct
9 Correct 139 ms 67204 KB Output is correct
10 Correct 142 ms 68500 KB Output is correct
11 Correct 148 ms 68436 KB Output is correct
12 Correct 174 ms 68800 KB Output is correct
13 Correct 134 ms 71876 KB Output is correct
14 Correct 142 ms 67332 KB Output is correct
15 Correct 312 ms 70268 KB Output is correct
16 Correct 273 ms 69964 KB Output is correct
17 Correct 360 ms 70388 KB Output is correct
18 Correct 447 ms 73540 KB Output is correct
19 Correct 345 ms 76172 KB Output is correct
20 Correct 352 ms 76700 KB Output is correct
21 Correct 403 ms 76700 KB Output is correct
22 Correct 333 ms 76552 KB Output is correct
23 Correct 364 ms 76756 KB Output is correct
24 Correct 366 ms 76152 KB Output is correct
25 Correct 389 ms 76612 KB Output is correct
26 Correct 316 ms 76136 KB Output is correct
27 Incorrect 32 ms 61424 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 61504 KB Output is correct
2 Correct 27 ms 61396 KB Output is correct
3 Correct 28 ms 61316 KB Output is correct
4 Correct 28 ms 61348 KB Output is correct
5 Correct 32 ms 61432 KB Output is correct
6 Correct 29 ms 61400 KB Output is correct
7 Correct 30 ms 61372 KB Output is correct
8 Correct 33 ms 61432 KB Output is correct
9 Correct 33 ms 61520 KB Output is correct
10 Correct 139 ms 67204 KB Output is correct
11 Correct 142 ms 68500 KB Output is correct
12 Correct 148 ms 68436 KB Output is correct
13 Correct 174 ms 68800 KB Output is correct
14 Correct 134 ms 71876 KB Output is correct
15 Correct 142 ms 67332 KB Output is correct
16 Correct 312 ms 70268 KB Output is correct
17 Correct 273 ms 69964 KB Output is correct
18 Correct 360 ms 70388 KB Output is correct
19 Correct 447 ms 73540 KB Output is correct
20 Correct 345 ms 76172 KB Output is correct
21 Correct 352 ms 76700 KB Output is correct
22 Correct 403 ms 76700 KB Output is correct
23 Correct 333 ms 76552 KB Output is correct
24 Correct 364 ms 76756 KB Output is correct
25 Correct 366 ms 76152 KB Output is correct
26 Correct 389 ms 76612 KB Output is correct
27 Correct 316 ms 76136 KB Output is correct
28 Incorrect 32 ms 61424 KB Output isn't correct
29 Halted 0 ms 0 KB -