oj.uz

Submission #571298

# Submission time Handle Problem Language Result Execution time Memory
571298 2022-06-01T16:45:10 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 427 ms 72508 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 5;
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 32 ms 55064 KB Output is correct
2 Correct 42 ms 55040 KB Output is correct
3 Correct 39 ms 55132 KB Output is correct
4 Correct 33 ms 55192 KB Output is correct
5 Correct 34 ms 55116 KB Output is correct
6 Correct 30 ms 55208 KB Output is correct
7 Correct 30 ms 55176 KB Output is correct
8 Correct 28 ms 55196 KB Output is correct
9 Correct 144 ms 61456 KB Output is correct
10 Correct 151 ms 62680 KB Output is correct
11 Correct 145 ms 62496 KB Output is correct
12 Correct 150 ms 62960 KB Output is correct
13 Correct 133 ms 66840 KB Output is correct
14 Correct 142 ms 61552 KB Output is correct
15 Correct 308 ms 64380 KB Output is correct
16 Correct 304 ms 64192 KB Output is correct
17 Correct 329 ms 64656 KB Output is correct
18 Correct 348 ms 68552 KB Output is correct
19 Correct 144 ms 60260 KB Output is correct
20 Correct 289 ms 64596 KB Output is correct
21 Correct 280 ms 64696 KB Output is correct
22 Correct 329 ms 65060 KB Output is correct
23 Correct 374 ms 68924 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55064 KB Output is correct
2 Correct 42 ms 55040 KB Output is correct
3 Correct 344 ms 71916 KB Output is correct
4 Correct 347 ms 72472 KB Output is correct
5 Correct 328 ms 72336 KB Output is correct
6 Correct 368 ms 72364 KB Output is correct
7 Correct 427 ms 72508 KB Output is correct
8 Correct 369 ms 71952 KB Output is correct
9 Correct 356 ms 72260 KB Output is correct
10 Correct 302 ms 71852 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55064 KB Output is correct
2 Correct 42 ms 55040 KB Output is correct
3 Correct 39 ms 55132 KB Output is correct
4 Correct 33 ms 55192 KB Output is correct
5 Correct 34 ms 55116 KB Output is correct
6 Correct 30 ms 55208 KB Output is correct
7 Correct 30 ms 55176 KB Output is correct
8 Correct 28 ms 55196 KB Output is correct
9 Correct 32 ms 55028 KB Output is correct
10 Correct 44 ms 55180 KB Output is correct
11 Incorrect 34 ms 55192 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55028 KB Output is correct
2 Correct 32 ms 55064 KB Output is correct
3 Correct 42 ms 55040 KB Output is correct
4 Correct 39 ms 55132 KB Output is correct
5 Correct 33 ms 55192 KB Output is correct
6 Correct 34 ms 55116 KB Output is correct
7 Correct 30 ms 55208 KB Output is correct
8 Correct 30 ms 55176 KB Output is correct
9 Correct 28 ms 55196 KB Output is correct
10 Correct 144 ms 61456 KB Output is correct
11 Correct 151 ms 62680 KB Output is correct
12 Correct 145 ms 62496 KB Output is correct
13 Correct 150 ms 62960 KB Output is correct
14 Correct 133 ms 66840 KB Output is correct
15 Correct 44 ms 55180 KB Output is correct
16 Incorrect 34 ms 55192 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55064 KB Output is correct
2 Correct 42 ms 55040 KB Output is correct
3 Correct 39 ms 55132 KB Output is correct
4 Correct 33 ms 55192 KB Output is correct
5 Correct 34 ms 55116 KB Output is correct
6 Correct 30 ms 55208 KB Output is correct
7 Correct 30 ms 55176 KB Output is correct
8 Correct 28 ms 55196 KB Output is correct
9 Correct 144 ms 61456 KB Output is correct
10 Correct 151 ms 62680 KB Output is correct
11 Correct 145 ms 62496 KB Output is correct
12 Correct 150 ms 62960 KB Output is correct
13 Correct 133 ms 66840 KB Output is correct
14 Correct 142 ms 61552 KB Output is correct
15 Correct 308 ms 64380 KB Output is correct
16 Correct 304 ms 64192 KB Output is correct
17 Correct 329 ms 64656 KB Output is correct
18 Correct 348 ms 68552 KB Output is correct
19 Correct 344 ms 71916 KB Output is correct
20 Correct 347 ms 72472 KB Output is correct
21 Correct 328 ms 72336 KB Output is correct
22 Correct 368 ms 72364 KB Output is correct
23 Correct 427 ms 72508 KB Output is correct
24 Correct 369 ms 71952 KB Output is correct
25 Correct 356 ms 72260 KB Output is correct
26 Correct 302 ms 71852 KB Output is correct
27 Correct 44 ms 55180 KB Output is correct
28 Incorrect 34 ms 55192 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55028 KB Output is correct
2 Correct 32 ms 55064 KB Output is correct
3 Correct 42 ms 55040 KB Output is correct
4 Correct 39 ms 55132 KB Output is correct
5 Correct 33 ms 55192 KB Output is correct
6 Correct 34 ms 55116 KB Output is correct
7 Correct 30 ms 55208 KB Output is correct
8 Correct 30 ms 55176 KB Output is correct
9 Correct 28 ms 55196 KB Output is correct
10 Correct 144 ms 61456 KB Output is correct
11 Correct 151 ms 62680 KB Output is correct
12 Correct 145 ms 62496 KB Output is correct
13 Correct 150 ms 62960 KB Output is correct
14 Correct 133 ms 66840 KB Output is correct
15 Correct 142 ms 61552 KB Output is correct
16 Correct 308 ms 64380 KB Output is correct
17 Correct 304 ms 64192 KB Output is correct
18 Correct 329 ms 64656 KB Output is correct
19 Correct 348 ms 68552 KB Output is correct
20 Correct 344 ms 71916 KB Output is correct
21 Correct 347 ms 72472 KB Output is correct
22 Correct 328 ms 72336 KB Output is correct
23 Correct 368 ms 72364 KB Output is correct
24 Correct 427 ms 72508 KB Output is correct
25 Correct 369 ms 71952 KB Output is correct
26 Correct 356 ms 72260 KB Output is correct
27 Correct 302 ms 71852 KB Output is correct
28 Correct 44 ms 55180 KB Output is correct
29 Incorrect 34 ms 55192 KB Output isn't correct
30 Halted 0 ms 0 KB -