oj.uz

Submission #571295

# Submission time Handle Problem Language Result Execution time Memory
571295 2022-06-01T16:41:09 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 447 ms 72376 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 = 20;
vector <int> ad [maxn];
int deg [maxn];
int dad [maxn];
vector <int> val (maxn, 1e9);
vector <bool> good (maxn, 0);
vector <int> cmp [maxn];
vector <int> depth (maxn);
int up[maxn][lg];
 
void dfs (int u, int vs) {
    if (good[u]) vs = val[u];
    val[u] = vs;
    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, vs);
    }
}
 
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] = (dad[x] == x ? x: get_dad(dad[x]));
}
 
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;
  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;
    }
  
  }
  propagate(extra);
  dfs(extra, 1e9);

}
 
int getMinimumFuelCapacity(int x, int y) {
  int k = lca(x,y);
  if (val[k] == 1e9) return -1;
  return val[k];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55084 KB Output is correct
2 Correct 41 ms 55052 KB Output is correct
3 Correct 49 ms 55104 KB Output is correct
4 Correct 31 ms 55124 KB Output is correct
5 Correct 35 ms 55188 KB Output is correct
6 Correct 32 ms 55204 KB Output is correct
7 Correct 38 ms 55192 KB Output is correct
8 Correct 39 ms 55148 KB Output is correct
9 Correct 168 ms 61004 KB Output is correct
10 Correct 155 ms 62204 KB Output is correct
11 Correct 158 ms 62164 KB Output is correct
12 Correct 185 ms 62468 KB Output is correct
13 Correct 195 ms 66428 KB Output is correct
14 Correct 141 ms 61216 KB Output is correct
15 Correct 300 ms 64208 KB Output is correct
16 Correct 330 ms 64068 KB Output is correct
17 Correct 303 ms 64544 KB Output is correct
18 Correct 374 ms 68396 KB Output is correct
19 Correct 121 ms 59880 KB Output is correct
20 Correct 319 ms 64516 KB Output is correct
21 Correct 302 ms 64644 KB Output is correct
22 Correct 304 ms 64884 KB Output is correct
23 Correct 447 ms 68800 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55084 KB Output is correct
2 Correct 41 ms 55052 KB Output is correct
3 Correct 348 ms 71792 KB Output is correct
4 Correct 322 ms 72324 KB Output is correct
5 Correct 423 ms 72224 KB Output is correct
6 Correct 356 ms 72300 KB Output is correct
7 Correct 364 ms 72376 KB Output is correct
8 Correct 368 ms 71744 KB Output is correct
9 Correct 356 ms 72276 KB Output is correct
10 Correct 377 ms 71716 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55084 KB Output is correct
2 Correct 41 ms 55052 KB Output is correct
3 Correct 49 ms 55104 KB Output is correct
4 Correct 31 ms 55124 KB Output is correct
5 Correct 35 ms 55188 KB Output is correct
6 Correct 32 ms 55204 KB Output is correct
7 Correct 38 ms 55192 KB Output is correct
8 Correct 39 ms 55148 KB Output is correct
9 Correct 31 ms 55112 KB Output is correct
10 Correct 31 ms 55228 KB Output is correct
11 Incorrect 33 ms 55128 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55112 KB Output is correct
2 Correct 31 ms 55084 KB Output is correct
3 Correct 41 ms 55052 KB Output is correct
4 Correct 49 ms 55104 KB Output is correct
5 Correct 31 ms 55124 KB Output is correct
6 Correct 35 ms 55188 KB Output is correct
7 Correct 32 ms 55204 KB Output is correct
8 Correct 38 ms 55192 KB Output is correct
9 Correct 39 ms 55148 KB Output is correct
10 Correct 168 ms 61004 KB Output is correct
11 Correct 155 ms 62204 KB Output is correct
12 Correct 158 ms 62164 KB Output is correct
13 Correct 185 ms 62468 KB Output is correct
14 Correct 195 ms 66428 KB Output is correct
15 Correct 31 ms 55228 KB Output is correct
16 Incorrect 33 ms 55128 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55084 KB Output is correct
2 Correct 41 ms 55052 KB Output is correct
3 Correct 49 ms 55104 KB Output is correct
4 Correct 31 ms 55124 KB Output is correct
5 Correct 35 ms 55188 KB Output is correct
6 Correct 32 ms 55204 KB Output is correct
7 Correct 38 ms 55192 KB Output is correct
8 Correct 39 ms 55148 KB Output is correct
9 Correct 168 ms 61004 KB Output is correct
10 Correct 155 ms 62204 KB Output is correct
11 Correct 158 ms 62164 KB Output is correct
12 Correct 185 ms 62468 KB Output is correct
13 Correct 195 ms 66428 KB Output is correct
14 Correct 141 ms 61216 KB Output is correct
15 Correct 300 ms 64208 KB Output is correct
16 Correct 330 ms 64068 KB Output is correct
17 Correct 303 ms 64544 KB Output is correct
18 Correct 374 ms 68396 KB Output is correct
19 Correct 348 ms 71792 KB Output is correct
20 Correct 322 ms 72324 KB Output is correct
21 Correct 423 ms 72224 KB Output is correct
22 Correct 356 ms 72300 KB Output is correct
23 Correct 364 ms 72376 KB Output is correct
24 Correct 368 ms 71744 KB Output is correct
25 Correct 356 ms 72276 KB Output is correct
26 Correct 377 ms 71716 KB Output is correct
27 Correct 31 ms 55228 KB Output is correct
28 Incorrect 33 ms 55128 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55112 KB Output is correct
2 Correct 31 ms 55084 KB Output is correct
3 Correct 41 ms 55052 KB Output is correct
4 Correct 49 ms 55104 KB Output is correct
5 Correct 31 ms 55124 KB Output is correct
6 Correct 35 ms 55188 KB Output is correct
7 Correct 32 ms 55204 KB Output is correct
8 Correct 38 ms 55192 KB Output is correct
9 Correct 39 ms 55148 KB Output is correct
10 Correct 168 ms 61004 KB Output is correct
11 Correct 155 ms 62204 KB Output is correct
12 Correct 158 ms 62164 KB Output is correct
13 Correct 185 ms 62468 KB Output is correct
14 Correct 195 ms 66428 KB Output is correct
15 Correct 141 ms 61216 KB Output is correct
16 Correct 300 ms 64208 KB Output is correct
17 Correct 330 ms 64068 KB Output is correct
18 Correct 303 ms 64544 KB Output is correct
19 Correct 374 ms 68396 KB Output is correct
20 Correct 348 ms 71792 KB Output is correct
21 Correct 322 ms 72324 KB Output is correct
22 Correct 423 ms 72224 KB Output is correct
23 Correct 356 ms 72300 KB Output is correct
24 Correct 364 ms 72376 KB Output is correct
25 Correct 368 ms 71744 KB Output is correct
26 Correct 356 ms 72276 KB Output is correct
27 Correct 377 ms 71716 KB Output is correct
28 Correct 31 ms 55228 KB Output is correct
29 Incorrect 33 ms 55128 KB Output isn't correct
30 Halted 0 ms 0 KB -