oj.uz

Submission #571300

# Submission time Handle Problem Language Result Execution time Memory
571300 2022-06-01T16:50:02 Z Vanilla Swapping Cities (APIO20_swap) C++17
13 / 100
 455 ms 57108 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, 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 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 + 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 10 ms 17876 KB Output is correct
2 Correct 11 ms 17940 KB Output is correct
3 Correct 9 ms 17876 KB Output is correct
4 Correct 9 ms 18088 KB Output is correct
5 Correct 10 ms 18260 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Correct 12 ms 18260 KB Output is correct
8 Correct 14 ms 18260 KB Output is correct
9 Correct 128 ms 41320 KB Output is correct
10 Correct 154 ms 46472 KB Output is correct
11 Correct 142 ms 46052 KB Output is correct
12 Correct 174 ms 47664 KB Output is correct
13 Correct 173 ms 51608 KB Output is correct
14 Correct 134 ms 41412 KB Output is correct
15 Correct 269 ms 48292 KB Output is correct
16 Correct 293 ms 47488 KB Output is correct
17 Correct 327 ms 49280 KB Output is correct
18 Correct 434 ms 53184 KB Output is correct
19 Correct 94 ms 25936 KB Output is correct
20 Correct 311 ms 48672 KB Output is correct
21 Correct 273 ms 47772 KB Output is correct
22 Correct 313 ms 49692 KB Output is correct
23 Correct 455 ms 53552 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 11 ms 17940 KB Output is correct
3 Correct 380 ms 55404 KB Output is correct
4 Correct 349 ms 57108 KB Output is correct
5 Correct 328 ms 56080 KB Output is correct
6 Correct 306 ms 56916 KB Output is correct
7 Correct 389 ms 56628 KB Output is correct
8 Correct 306 ms 55160 KB Output is correct
9 Correct 338 ms 56288 KB Output is correct
10 Correct 334 ms 54912 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 11 ms 17940 KB Output is correct
3 Correct 9 ms 17876 KB Output is correct
4 Correct 9 ms 18088 KB Output is correct
5 Correct 10 ms 18260 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Correct 12 ms 18260 KB Output is correct
8 Correct 14 ms 18260 KB Output is correct
9 Correct 11 ms 17876 KB Output is correct
10 Correct 10 ms 18260 KB Output is correct
11 Incorrect 11 ms 18216 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 10 ms 17876 KB Output is correct
3 Correct 11 ms 17940 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 18088 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Correct 14 ms 18260 KB Output is correct
10 Correct 128 ms 41320 KB Output is correct
11 Correct 154 ms 46472 KB Output is correct
12 Correct 142 ms 46052 KB Output is correct
13 Correct 174 ms 47664 KB Output is correct
14 Correct 173 ms 51608 KB Output is correct
15 Correct 10 ms 18260 KB Output is correct
16 Incorrect 11 ms 18216 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17876 KB Output is correct
2 Correct 11 ms 17940 KB Output is correct
3 Correct 9 ms 17876 KB Output is correct
4 Correct 9 ms 18088 KB Output is correct
5 Correct 10 ms 18260 KB Output is correct
6 Correct 11 ms 18260 KB Output is correct
7 Correct 12 ms 18260 KB Output is correct
8 Correct 14 ms 18260 KB Output is correct
9 Correct 128 ms 41320 KB Output is correct
10 Correct 154 ms 46472 KB Output is correct
11 Correct 142 ms 46052 KB Output is correct
12 Correct 174 ms 47664 KB Output is correct
13 Correct 173 ms 51608 KB Output is correct
14 Correct 134 ms 41412 KB Output is correct
15 Correct 269 ms 48292 KB Output is correct
16 Correct 293 ms 47488 KB Output is correct
17 Correct 327 ms 49280 KB Output is correct
18 Correct 434 ms 53184 KB Output is correct
19 Correct 380 ms 55404 KB Output is correct
20 Correct 349 ms 57108 KB Output is correct
21 Correct 328 ms 56080 KB Output is correct
22 Correct 306 ms 56916 KB Output is correct
23 Correct 389 ms 56628 KB Output is correct
24 Correct 306 ms 55160 KB Output is correct
25 Correct 338 ms 56288 KB Output is correct
26 Correct 334 ms 54912 KB Output is correct
27 Correct 10 ms 18260 KB Output is correct
28 Incorrect 11 ms 18216 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 17876 KB Output is correct
2 Correct 10 ms 17876 KB Output is correct
3 Correct 11 ms 17940 KB Output is correct
4 Correct 9 ms 17876 KB Output is correct
5 Correct 9 ms 18088 KB Output is correct
6 Correct 10 ms 18260 KB Output is correct
7 Correct 11 ms 18260 KB Output is correct
8 Correct 12 ms 18260 KB Output is correct
9 Correct 14 ms 18260 KB Output is correct
10 Correct 128 ms 41320 KB Output is correct
11 Correct 154 ms 46472 KB Output is correct
12 Correct 142 ms 46052 KB Output is correct
13 Correct 174 ms 47664 KB Output is correct
14 Correct 173 ms 51608 KB Output is correct
15 Correct 134 ms 41412 KB Output is correct
16 Correct 269 ms 48292 KB Output is correct
17 Correct 293 ms 47488 KB Output is correct
18 Correct 327 ms 49280 KB Output is correct
19 Correct 434 ms 53184 KB Output is correct
20 Correct 380 ms 55404 KB Output is correct
21 Correct 349 ms 57108 KB Output is correct
22 Correct 328 ms 56080 KB Output is correct
23 Correct 306 ms 56916 KB Output is correct
24 Correct 389 ms 56628 KB Output is correct
25 Correct 306 ms 55160 KB Output is correct
26 Correct 338 ms 56288 KB Output is correct
27 Correct 334 ms 54912 KB Output is correct
28 Correct 10 ms 18260 KB Output is correct
29 Incorrect 11 ms 18216 KB Output isn't correct
30 Halted 0 ms 0 KB -