oj.uz

Submission #674622

# Submission time Handle Problem Language Result Execution time Memory
674622 2022-12-25T12:37:55 Z Vahe Swapping Cities (APIO20_swap) C++17
7 / 100
 2000 ms 12532 KB 
#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
vector<vector<pair<int, int>>> gp;
int n, m;
vector<int> u, v, w, ver, var, par, P, p, her, sizes;

int get(int u)
{
    if (u == par[u]) return u;
    return par[u] = get(par[u]);
}

void union_chains(int u, int v, int w)
{
    if (get(u) == get(v))
    {
        P[get(u)] = min(P[get(u)], w);
        return;
    }
    int a = get(u), b = get(v);
    if (sizes[a] < sizes[b]) swap(a, b), swap(u, v);
    sizes[a] += sizes[b];
    par[b] = par[a];
    her[v] = w, p[v] = u;
    if      (u == ver[a] && v == ver[b]) ver[a] = var[b];
    else if (u == ver[a] && v == var[b]) ver[a] = ver[b];
    else if (u == var[a] && v == ver[b]) var[a] = var[b];
    else if (u == var[a] && v == var[b]) var[a] = ver[b];
    else ver[a] = -1, var[a] = -1, P[u] = min(P[u], w);
}

int go(int u, int w)
{
    if (p[u] == u || her[u] > w) return u;
    return go(p[u], w);
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N, m = M;
    vector<pair<int, pair<int, int>>> kox;
    for (int i = 0; i < m; i++) kox.push_back({ W[i], {U[i], V[i]} });
    sort(kox.begin(), kox.end());
    ver = var = par = sizes = P = her = p = vector<int>(n);
    for (int i = 0; i < n; i++) ver[i] = var[i] = par[i] = p[i] = i, sizes[i] = 1, her[i] = P[i] = INT_MAX;
    for (int i = 0; i < m; i++)
    {
        int u = kox[i].second.first, v = kox[i].second.second;
        union_chains(u, v, kox[i].first);
    }

}

int getMinimumFuelCapacity(int X, int Y) {
    long long l = -1, r = 2e9;
    while (l + 1 < r)
    {
        int mij = l + (r - l) / 2;
        int a = go(X, mij), b = go(Y, mij);
        if (a == b && P[a] <= mij) r = mij;
        else l = mij;
    }
    return r != 2e9 ? r : -1;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 36 ms 6832 KB Output is correct
10 Correct 43 ms 8296 KB Output is correct
11 Correct 43 ms 8168 KB Output is correct
12 Correct 44 ms 8604 KB Output is correct
13 Correct 101 ms 8604 KB Output is correct
14 Correct 46 ms 7104 KB Output is correct
15 Correct 133 ms 12184 KB Output is correct
16 Correct 131 ms 11968 KB Output is correct
17 Correct 136 ms 12456 KB Output is correct
18 Execution timed out 2062 ms 12532 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 143 ms 11936 KB Output is correct
4 Correct 138 ms 12044 KB Output is correct
5 Correct 154 ms 12288 KB Output is correct
6 Correct 140 ms 12012 KB Output is correct
7 Correct 147 ms 12232 KB Output is correct
8 Correct 143 ms 11932 KB Output is correct
9 Correct 155 ms 11988 KB Output is correct
10 Correct 149 ms 12080 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 1 ms 312 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 36 ms 6832 KB Output is correct
11 Correct 43 ms 8296 KB Output is correct
12 Correct 43 ms 8168 KB Output is correct
13 Correct 44 ms 8604 KB Output is correct
14 Correct 101 ms 8604 KB Output is correct
15 Incorrect 1 ms 312 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 36 ms 6832 KB Output is correct
10 Correct 43 ms 8296 KB Output is correct
11 Correct 43 ms 8168 KB Output is correct
12 Correct 44 ms 8604 KB Output is correct
13 Correct 101 ms 8604 KB Output is correct
14 Correct 46 ms 7104 KB Output is correct
15 Correct 133 ms 12184 KB Output is correct
16 Correct 131 ms 11968 KB Output is correct
17 Correct 136 ms 12456 KB Output is correct
18 Execution timed out 2062 ms 12532 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 36 ms 6832 KB Output is correct
11 Correct 43 ms 8296 KB Output is correct
12 Correct 43 ms 8168 KB Output is correct
13 Correct 44 ms 8604 KB Output is correct
14 Correct 101 ms 8604 KB Output is correct
15 Correct 46 ms 7104 KB Output is correct
16 Correct 133 ms 12184 KB Output is correct
17 Correct 131 ms 11968 KB Output is correct
18 Correct 136 ms 12456 KB Output is correct
19 Execution timed out 2062 ms 12532 KB Time limit exceeded
20 Halted 0 ms 0 KB -