oj.uz

Submission #571290

# Submission time Handle Problem Language Result Execution time Memory
571290 2022-06-01T16:25:57 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 429 ms 78672 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 && 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]));
}
 
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 (!good[k] || k == maxn - 1 || val[k] == 1e9) return -1;
  return val[k];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 61332 KB Output is correct
2 Correct 29 ms 61372 KB Output is correct
3 Correct 29 ms 61340 KB Output is correct
4 Correct 30 ms 61340 KB Output is correct
5 Correct 31 ms 61484 KB Output is correct
6 Correct 29 ms 61460 KB Output is correct
7 Correct 31 ms 61388 KB Output is correct
8 Correct 30 ms 61516 KB Output is correct
9 Correct 131 ms 67448 KB Output is correct
10 Correct 147 ms 68832 KB Output is correct
11 Correct 145 ms 68804 KB Output is correct
12 Correct 157 ms 69252 KB Output is correct
13 Correct 162 ms 73084 KB Output is correct
14 Correct 133 ms 67612 KB Output is correct
15 Correct 278 ms 70504 KB Output is correct
16 Correct 268 ms 70212 KB Output is correct
17 Correct 290 ms 70812 KB Output is correct
18 Correct 429 ms 74692 KB Output is correct
19 Correct 127 ms 65952 KB Output is correct
20 Correct 289 ms 70780 KB Output is correct
21 Correct 282 ms 70836 KB Output is correct
22 Correct 293 ms 71164 KB Output is correct
23 Correct 419 ms 75152 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 61332 KB Output is correct
2 Correct 29 ms 61372 KB Output is correct
3 Correct 357 ms 78088 KB Output is correct
4 Correct 314 ms 78608 KB Output is correct
5 Correct 372 ms 78576 KB Output is correct
6 Correct 312 ms 78548 KB Output is correct
7 Correct 405 ms 78672 KB Output is correct
8 Correct 350 ms 78076 KB Output is correct
9 Correct 354 ms 78500 KB Output is correct
10 Correct 350 ms 77948 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 61332 KB Output is correct
2 Correct 29 ms 61372 KB Output is correct
3 Correct 29 ms 61340 KB Output is correct
4 Correct 30 ms 61340 KB Output is correct
5 Correct 31 ms 61484 KB Output is correct
6 Correct 29 ms 61460 KB Output is correct
7 Correct 31 ms 61388 KB Output is correct
8 Correct 30 ms 61516 KB Output is correct
9 Correct 32 ms 61396 KB Output is correct
10 Incorrect 31 ms 61396 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61396 KB Output is correct
2 Correct 33 ms 61332 KB Output is correct
3 Correct 29 ms 61372 KB Output is correct
4 Correct 29 ms 61340 KB Output is correct
5 Correct 30 ms 61340 KB Output is correct
6 Correct 31 ms 61484 KB Output is correct
7 Correct 29 ms 61460 KB Output is correct
8 Correct 31 ms 61388 KB Output is correct
9 Correct 30 ms 61516 KB Output is correct
10 Correct 131 ms 67448 KB Output is correct
11 Correct 147 ms 68832 KB Output is correct
12 Correct 145 ms 68804 KB Output is correct
13 Correct 157 ms 69252 KB Output is correct
14 Correct 162 ms 73084 KB Output is correct
15 Incorrect 31 ms 61396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 61332 KB Output is correct
2 Correct 29 ms 61372 KB Output is correct
3 Correct 29 ms 61340 KB Output is correct
4 Correct 30 ms 61340 KB Output is correct
5 Correct 31 ms 61484 KB Output is correct
6 Correct 29 ms 61460 KB Output is correct
7 Correct 31 ms 61388 KB Output is correct
8 Correct 30 ms 61516 KB Output is correct
9 Correct 131 ms 67448 KB Output is correct
10 Correct 147 ms 68832 KB Output is correct
11 Correct 145 ms 68804 KB Output is correct
12 Correct 157 ms 69252 KB Output is correct
13 Correct 162 ms 73084 KB Output is correct
14 Correct 133 ms 67612 KB Output is correct
15 Correct 278 ms 70504 KB Output is correct
16 Correct 268 ms 70212 KB Output is correct
17 Correct 290 ms 70812 KB Output is correct
18 Correct 429 ms 74692 KB Output is correct
19 Correct 357 ms 78088 KB Output is correct
20 Correct 314 ms 78608 KB Output is correct
21 Correct 372 ms 78576 KB Output is correct
22 Correct 312 ms 78548 KB Output is correct
23 Correct 405 ms 78672 KB Output is correct
24 Correct 350 ms 78076 KB Output is correct
25 Correct 354 ms 78500 KB Output is correct
26 Correct 350 ms 77948 KB Output is correct
27 Incorrect 31 ms 61396 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 61396 KB Output is correct
2 Correct 33 ms 61332 KB Output is correct
3 Correct 29 ms 61372 KB Output is correct
4 Correct 29 ms 61340 KB Output is correct
5 Correct 30 ms 61340 KB Output is correct
6 Correct 31 ms 61484 KB Output is correct
7 Correct 29 ms 61460 KB Output is correct
8 Correct 31 ms 61388 KB Output is correct
9 Correct 30 ms 61516 KB Output is correct
10 Correct 131 ms 67448 KB Output is correct
11 Correct 147 ms 68832 KB Output is correct
12 Correct 145 ms 68804 KB Output is correct
13 Correct 157 ms 69252 KB Output is correct
14 Correct 162 ms 73084 KB Output is correct
15 Correct 133 ms 67612 KB Output is correct
16 Correct 278 ms 70504 KB Output is correct
17 Correct 268 ms 70212 KB Output is correct
18 Correct 290 ms 70812 KB Output is correct
19 Correct 429 ms 74692 KB Output is correct
20 Correct 357 ms 78088 KB Output is correct
21 Correct 314 ms 78608 KB Output is correct
22 Correct 372 ms 78576 KB Output is correct
23 Correct 312 ms 78548 KB Output is correct
24 Correct 405 ms 78672 KB Output is correct
25 Correct 350 ms 78076 KB Output is correct
26 Correct 354 ms 78500 KB Output is correct
27 Correct 350 ms 77948 KB Output is correct
28 Incorrect 31 ms 61396 KB Output isn't correct
29 Halted 0 ms 0 KB -