oj.uz

Submission #571305

# Submission time Handle Problem Language Result Execution time Memory
571305 2022-06-01T16:58:43 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 490 ms 56756 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 200;
int extra = 1e5 + 1;
const int lg = 29;
vector <int> ad [maxn];
int deg [maxn];
int dad [maxn];
vector <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;
  for (int i = 1; i <= n; i++){
    dad[i] = i;
    val[i] = 1e9;
  }
  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;
    dad[extra] = extra;
    cmp[extra].push_back(p1);
    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 + 1,y + 1);
  if (val[k] == 1e9) return -1;
  return val[k];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16724 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 11 ms 16956 KB Output is correct
5 Correct 12 ms 17108 KB Output is correct
6 Correct 10 ms 17028 KB Output is correct
7 Correct 10 ms 17132 KB Output is correct
8 Correct 11 ms 17108 KB Output is correct
9 Correct 115 ms 40752 KB Output is correct
10 Correct 143 ms 46124 KB Output is correct
11 Correct 156 ms 45584 KB Output is correct
12 Correct 146 ms 47412 KB Output is correct
13 Correct 157 ms 51128 KB Output is correct
14 Correct 126 ms 40896 KB Output is correct
15 Correct 286 ms 47876 KB Output is correct
16 Correct 256 ms 47016 KB Output is correct
17 Correct 293 ms 48820 KB Output is correct
18 Correct 398 ms 52692 KB Output is correct
19 Correct 123 ms 24880 KB Output is correct
20 Correct 340 ms 48260 KB Output is correct
21 Correct 337 ms 47416 KB Output is correct
22 Correct 352 ms 49284 KB Output is correct
23 Correct 490 ms 53220 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16724 KB Output is correct
3 Correct 324 ms 54920 KB Output is correct
4 Correct 372 ms 56756 KB Output is correct
5 Correct 374 ms 55680 KB Output is correct
6 Correct 335 ms 56540 KB Output is correct
7 Correct 353 ms 56236 KB Output is correct
8 Correct 328 ms 54728 KB Output is correct
9 Correct 319 ms 55880 KB Output is correct
10 Correct 345 ms 54388 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16724 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 11 ms 16956 KB Output is correct
5 Correct 12 ms 17108 KB Output is correct
6 Correct 10 ms 17028 KB Output is correct
7 Correct 10 ms 17132 KB Output is correct
8 Correct 11 ms 17108 KB Output is correct
9 Correct 9 ms 16724 KB Output is correct
10 Correct 9 ms 17108 KB Output is correct
11 Incorrect 10 ms 17108 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 11 ms 16956 KB Output is correct
6 Correct 12 ms 17108 KB Output is correct
7 Correct 10 ms 17028 KB Output is correct
8 Correct 10 ms 17132 KB Output is correct
9 Correct 11 ms 17108 KB Output is correct
10 Correct 115 ms 40752 KB Output is correct
11 Correct 143 ms 46124 KB Output is correct
12 Correct 156 ms 45584 KB Output is correct
13 Correct 146 ms 47412 KB Output is correct
14 Correct 157 ms 51128 KB Output is correct
15 Correct 9 ms 17108 KB Output is correct
16 Incorrect 10 ms 17108 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 10 ms 16724 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 11 ms 16956 KB Output is correct
5 Correct 12 ms 17108 KB Output is correct
6 Correct 10 ms 17028 KB Output is correct
7 Correct 10 ms 17132 KB Output is correct
8 Correct 11 ms 17108 KB Output is correct
9 Correct 115 ms 40752 KB Output is correct
10 Correct 143 ms 46124 KB Output is correct
11 Correct 156 ms 45584 KB Output is correct
12 Correct 146 ms 47412 KB Output is correct
13 Correct 157 ms 51128 KB Output is correct
14 Correct 126 ms 40896 KB Output is correct
15 Correct 286 ms 47876 KB Output is correct
16 Correct 256 ms 47016 KB Output is correct
17 Correct 293 ms 48820 KB Output is correct
18 Correct 398 ms 52692 KB Output is correct
19 Correct 324 ms 54920 KB Output is correct
20 Correct 372 ms 56756 KB Output is correct
21 Correct 374 ms 55680 KB Output is correct
22 Correct 335 ms 56540 KB Output is correct
23 Correct 353 ms 56236 KB Output is correct
24 Correct 328 ms 54728 KB Output is correct
25 Correct 319 ms 55880 KB Output is correct
26 Correct 345 ms 54388 KB Output is correct
27 Correct 9 ms 17108 KB Output is correct
28 Incorrect 10 ms 17108 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 10 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 11 ms 16956 KB Output is correct
6 Correct 12 ms 17108 KB Output is correct
7 Correct 10 ms 17028 KB Output is correct
8 Correct 10 ms 17132 KB Output is correct
9 Correct 11 ms 17108 KB Output is correct
10 Correct 115 ms 40752 KB Output is correct
11 Correct 143 ms 46124 KB Output is correct
12 Correct 156 ms 45584 KB Output is correct
13 Correct 146 ms 47412 KB Output is correct
14 Correct 157 ms 51128 KB Output is correct
15 Correct 126 ms 40896 KB Output is correct
16 Correct 286 ms 47876 KB Output is correct
17 Correct 256 ms 47016 KB Output is correct
18 Correct 293 ms 48820 KB Output is correct
19 Correct 398 ms 52692 KB Output is correct
20 Correct 324 ms 54920 KB Output is correct
21 Correct 372 ms 56756 KB Output is correct
22 Correct 374 ms 55680 KB Output is correct
23 Correct 335 ms 56540 KB Output is correct
24 Correct 353 ms 56236 KB Output is correct
25 Correct 328 ms 54728 KB Output is correct
26 Correct 319 ms 55880 KB Output is correct
27 Correct 345 ms 54388 KB Output is correct
28 Correct 9 ms 17108 KB Output is correct
29 Incorrect 10 ms 17108 KB Output isn't correct
30 Halted 0 ms 0 KB -