oj.uz

Submission #571291

# Submission time Handle Problem Language Result Execution time Memory
571291 2022-06-01T16:27:46 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 401 ms 78688 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, 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;
  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, 1e9);
      break;
    }
  }
 
}
 
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 30 ms 61396 KB Output is correct
2 Correct 31 ms 61312 KB Output is correct
3 Correct 33 ms 61292 KB Output is correct
4 Correct 30 ms 61408 KB Output is correct
5 Correct 30 ms 61396 KB Output is correct
6 Correct 31 ms 61500 KB Output is correct
7 Correct 30 ms 61436 KB Output is correct
8 Correct 31 ms 61456 KB Output is correct
9 Correct 123 ms 67444 KB Output is correct
10 Correct 147 ms 68936 KB Output is correct
11 Correct 145 ms 68804 KB Output is correct
12 Correct 151 ms 69244 KB Output is correct
13 Correct 155 ms 73168 KB Output is correct
14 Correct 137 ms 67648 KB Output is correct
15 Correct 268 ms 70512 KB Output is correct
16 Correct 270 ms 70212 KB Output is correct
17 Correct 266 ms 70808 KB Output is correct
18 Correct 401 ms 74716 KB Output is correct
19 Correct 114 ms 65948 KB Output is correct
20 Correct 255 ms 70800 KB Output is correct
21 Correct 272 ms 70892 KB Output is correct
22 Correct 264 ms 71180 KB Output is correct
23 Correct 382 ms 75064 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 61396 KB Output is correct
2 Correct 31 ms 61312 KB Output is correct
3 Correct 292 ms 78088 KB Output is correct
4 Correct 314 ms 78688 KB Output is correct
5 Correct 313 ms 78444 KB Output is correct
6 Correct 343 ms 78556 KB Output is correct
7 Correct 356 ms 78676 KB Output is correct
8 Correct 351 ms 78060 KB Output is correct
9 Correct 349 ms 78484 KB Output is correct
10 Correct 367 ms 77944 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 61396 KB Output is correct
2 Correct 31 ms 61312 KB Output is correct
3 Correct 33 ms 61292 KB Output is correct
4 Correct 30 ms 61408 KB Output is correct
5 Correct 30 ms 61396 KB Output is correct
6 Correct 31 ms 61500 KB Output is correct
7 Correct 30 ms 61436 KB Output is correct
8 Correct 31 ms 61456 KB Output is correct
9 Correct 38 ms 61388 KB Output is correct
10 Correct 33 ms 61420 KB Output is correct
11 Incorrect 41 ms 61428 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 61388 KB Output is correct
2 Correct 30 ms 61396 KB Output is correct
3 Correct 31 ms 61312 KB Output is correct
4 Correct 33 ms 61292 KB Output is correct
5 Correct 30 ms 61408 KB Output is correct
6 Correct 30 ms 61396 KB Output is correct
7 Correct 31 ms 61500 KB Output is correct
8 Correct 30 ms 61436 KB Output is correct
9 Correct 31 ms 61456 KB Output is correct
10 Correct 123 ms 67444 KB Output is correct
11 Correct 147 ms 68936 KB Output is correct
12 Correct 145 ms 68804 KB Output is correct
13 Correct 151 ms 69244 KB Output is correct
14 Correct 155 ms 73168 KB Output is correct
15 Correct 33 ms 61420 KB Output is correct
16 Incorrect 41 ms 61428 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 61396 KB Output is correct
2 Correct 31 ms 61312 KB Output is correct
3 Correct 33 ms 61292 KB Output is correct
4 Correct 30 ms 61408 KB Output is correct
5 Correct 30 ms 61396 KB Output is correct
6 Correct 31 ms 61500 KB Output is correct
7 Correct 30 ms 61436 KB Output is correct
8 Correct 31 ms 61456 KB Output is correct
9 Correct 123 ms 67444 KB Output is correct
10 Correct 147 ms 68936 KB Output is correct
11 Correct 145 ms 68804 KB Output is correct
12 Correct 151 ms 69244 KB Output is correct
13 Correct 155 ms 73168 KB Output is correct
14 Correct 137 ms 67648 KB Output is correct
15 Correct 268 ms 70512 KB Output is correct
16 Correct 270 ms 70212 KB Output is correct
17 Correct 266 ms 70808 KB Output is correct
18 Correct 401 ms 74716 KB Output is correct
19 Correct 292 ms 78088 KB Output is correct
20 Correct 314 ms 78688 KB Output is correct
21 Correct 313 ms 78444 KB Output is correct
22 Correct 343 ms 78556 KB Output is correct
23 Correct 356 ms 78676 KB Output is correct
24 Correct 351 ms 78060 KB Output is correct
25 Correct 349 ms 78484 KB Output is correct
26 Correct 367 ms 77944 KB Output is correct
27 Correct 33 ms 61420 KB Output is correct
28 Incorrect 41 ms 61428 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 61388 KB Output is correct
2 Correct 30 ms 61396 KB Output is correct
3 Correct 31 ms 61312 KB Output is correct
4 Correct 33 ms 61292 KB Output is correct
5 Correct 30 ms 61408 KB Output is correct
6 Correct 30 ms 61396 KB Output is correct
7 Correct 31 ms 61500 KB Output is correct
8 Correct 30 ms 61436 KB Output is correct
9 Correct 31 ms 61456 KB Output is correct
10 Correct 123 ms 67444 KB Output is correct
11 Correct 147 ms 68936 KB Output is correct
12 Correct 145 ms 68804 KB Output is correct
13 Correct 151 ms 69244 KB Output is correct
14 Correct 155 ms 73168 KB Output is correct
15 Correct 137 ms 67648 KB Output is correct
16 Correct 268 ms 70512 KB Output is correct
17 Correct 270 ms 70212 KB Output is correct
18 Correct 266 ms 70808 KB Output is correct
19 Correct 401 ms 74716 KB Output is correct
20 Correct 292 ms 78088 KB Output is correct
21 Correct 314 ms 78688 KB Output is correct
22 Correct 313 ms 78444 KB Output is correct
23 Correct 343 ms 78556 KB Output is correct
24 Correct 356 ms 78676 KB Output is correct
25 Correct 351 ms 78060 KB Output is correct
26 Correct 349 ms 78484 KB Output is correct
27 Correct 367 ms 77944 KB Output is correct
28 Correct 33 ms 61420 KB Output is correct
29 Incorrect 41 ms 61428 KB Output isn't correct
30 Halted 0 ms 0 KB -