oj.uz

Submission #875315

# Submission time Handle Problem Language Result Execution time Memory
875315 2023-11-19T05:36:05 Z sleepntsheep Swapping Cities (APIO20_swap) C++17
17 / 100
 68 ms 33732 KB 
#include "swap.h"
#include <iostream>
#include <tuple>
#include <algorithm> 
#include <vector>

using namespace std;
#define N 100000
#define M 200000

vector<int> g[N];
int p[N+M], P[N+M], J[N+M], D[N+M], d[N+M], f[N+M], l, V[N+M], W[N+M];

int fnd(int x) { return p[x] == x ? x : p[x] = fnd(p[x]); }

void link(int w, int u, int v)
{
    int ru = fnd(u), rv = fnd(v), sw = f[ru] | f[rv];
    if (ru == rv) { if (f[ru]) return; f[ru] = 1; W[ru] = w; return; }
    if (++d[u] >= 3 || ++d[v] >= 3) sw = 1;
    u = ru, v = rv;
    p[u] = p[v] = l; W[l] = w;
    g[l].push_back(u), g[l].push_back(v);
    f[l++] = sw;
}

void dfs(int u)
{
    V[u] = 1;
    for (auto v : g[u]) if (!V[v])
    {
        P[v] = u; D[v] = D[u] + 1;
        J[v] = (D[u] - D[J[u]] == D[J[u]] - D[J[J[u]]] ? J[J[u]] : u);
        dfs(v);
    }
}

int lca(int u, int v)
{
    if (D[u] < D[v]) return lca(v, u);
    if (fnd(u) != fnd(v)) return -1;
    while (D[u] > D[v])
    {
        if (D[J[u]] >= D[v]) u = J[u];
        else u = P[u];
    }
    while (u != v)
    {
        if (J[u] == J[v]) u = P[u], v = P[v];
        else u = J[u], v = J[v];
    }
    return u;
}

int lowest_switchable(int u)
{
    while (!f[u] && u != P[u])
        if (f[J[u]]) u = P[u];
        else u = J[u];
    return u;
}

void init(int n, int m, std::vector<int> u, std::vector<int> v, std::vector<int> w)
{
    vector<tuple<int, int, int>> e;
    l = n;
    for (int i = 0; i < u.size(); ++i) e.emplace_back(w[i], u[i], v[i]); 
    sort(e.begin(), e.end());
    for (int i = 0; i < n + m; ++i) p[i] = i;

    for (auto &[w, u, v] : e) link(w, u, v);
    for (int i = l; --i; ) if (!V[i])
        dfs(P[i] = J[i] = i);
}

int getMinimumFuelCapacity(int x, int y)
{
    int a = lca(x, y);
    if (a == -1) return -1;
    int b = lowest_switchable(a);
    if (!f[b]) return -1;
    return W[b];
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < u.size(); ++i) e.emplace_back(w[i], u[i], v[i]);
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 10076 KB Output is correct
9 Runtime error 37 ms 28356 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Runtime error 68 ms 33732 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 10076 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Correct 2 ms 9952 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 10044 KB Output is correct
13 Correct 3 ms 9820 KB Output is correct
14 Correct 2 ms 9816 KB Output is correct
15 Correct 2 ms 9820 KB Output is correct
16 Correct 2 ms 9820 KB Output is correct
17 Correct 2 ms 10076 KB Output is correct
18 Correct 2 ms 9820 KB Output is correct
19 Correct 2 ms 9972 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 3 ms 10076 KB Output is correct
22 Correct 2 ms 10076 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 2 ms 10076 KB Output is correct
25 Correct 3 ms 10076 KB Output is correct
26 Correct 2 ms 10076 KB Output is correct
27 Correct 2 ms 10076 KB Output is correct
28 Correct 3 ms 9952 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9816 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 10076 KB Output is correct
10 Runtime error 37 ms 28356 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 10076 KB Output is correct
9 Runtime error 37 ms 28356 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9816 KB Output is correct
8 Correct 2 ms 9820 KB Output is correct
9 Correct 2 ms 10076 KB Output is correct
10 Runtime error 37 ms 28356 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -