oj.uz

Submission #467340

# Submission time Handle Problem Language Result Execution time Memory
467340 2021-08-22T16:50:15 Z SirCovidThe19th Swapping Cities (APIO20_swap) C++17
6 / 100
 411 ms 41464 KB 
#include <bits/stdc++.h>
using namespace std; 

const int mx = 3e5 + 5;

int node, par[mx], up[mx][19], vals[mx], dep[mx]; bool ok[mx][19], cyc[mx]; 
vector<int> adj[mx];

int get(int i){
    return i == par[i] ? i : par[i] = get(par[i]);
}
void merge(int a, int b){
    a = get(a); b = get(b);
    cyc[node] = (a == b) or cyc[a] or cyc[b];
    adj[node].push_back(a); if (a != b) adj[node].push_back(b);
    par[a] = par[b] = node++;
}
void dfs(int i){
    for (int l = 1; l < 19; l++){
        up[i][l] = up[up[i][l - 1]][l - 1];
        ok[i][l] = ok[up[i][l - 1]][l - 1] | ok[i][l - 1];
    }
    for (auto x : adj[i]){
        up[x][0] = i; ok[x][0] = cyc[i];
        dep[x] = dep[i] + 1; dfs(x);
    }
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w){
    int idx[m]; node = n + 1; iota(idx, idx + m, 0); iota(par, par + n + m + 1, 0); 
    sort(idx, idx + m, [&](int a, int b){ return w[a] < w[b]; });
    for (int i : idx){
        vals[node] = w[i]; 
        merge(u[i] + 1, v[i] + 1);
    }
    for (int i = n + m; i > 0; i--) 
        if (!up[i][0]) dfs(i); 
}
int getMinimumFuelCapacity(int x, int y){
    x++; y++; if (dep[x] < dep[y]) swap(x, y);
    for (int i = 18; i >= 0; i--)
        if (((dep[x] - dep[y]) >> i) & 1) x = up[x][i];
    for (int i = 18; i >= 0; i--)
        if (up[x][i] != up[y][i] or (!ok[x][i] and !ok[y][i] and !(cyc[x] and cyc[y]))) 
            x = up[x][i], y = up[y][i];
    int L = (x != y or !(cyc[x] and cyc[y])) ? up[x][0] : x;
    return (!L or x != y) ? -1 : vals[L];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7628 KB Output is correct
8 Correct 5 ms 7628 KB Output is correct
9 Correct 118 ms 28176 KB Output is correct
10 Correct 138 ms 32912 KB Output is correct
11 Correct 137 ms 32384 KB Output is correct
12 Correct 155 ms 33800 KB Output is correct
13 Correct 140 ms 37824 KB Output is correct
14 Correct 127 ms 28260 KB Output is correct
15 Correct 276 ms 34752 KB Output is correct
16 Correct 277 ms 34112 KB Output is correct
17 Correct 284 ms 35572 KB Output is correct
18 Correct 390 ms 39588 KB Output is correct
19 Correct 101 ms 14916 KB Output is correct
20 Correct 272 ms 35988 KB Output is correct
21 Correct 278 ms 35260 KB Output is correct
22 Correct 297 ms 37044 KB Output is correct
23 Correct 411 ms 40896 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Incorrect 334 ms 41464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7628 KB Output is correct
8 Correct 5 ms 7628 KB Output is correct
9 Incorrect 4 ms 7372 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7372 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 5 ms 7628 KB Output is correct
8 Correct 5 ms 7628 KB Output is correct
9 Correct 118 ms 28176 KB Output is correct
10 Correct 138 ms 32912 KB Output is correct
11 Correct 137 ms 32384 KB Output is correct
12 Correct 155 ms 33800 KB Output is correct
13 Correct 140 ms 37824 KB Output is correct
14 Correct 127 ms 28260 KB Output is correct
15 Correct 276 ms 34752 KB Output is correct
16 Correct 277 ms 34112 KB Output is correct
17 Correct 284 ms 35572 KB Output is correct
18 Correct 390 ms 39588 KB Output is correct
19 Incorrect 334 ms 41464 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7372 KB Output isn't correct