oj.uz

Submission #551007

# Submission time Handle Problem Language Result Execution time Memory
551007 2022-04-19T17:35:54 Z hoanghq2004 Swapping Cities (APIO20_swap) C++14
36 / 100
 302 ms 39792 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define Submit
#ifdef Submit
#include "swap.h"

#endif // Submit

using namespace __gnu_pbds;
using namespace std;

const int N = 2e5 + 10;

int n;
int deg[N];
int root[N], ok[N];
vector <int> g[N];
int par[N][20];
int in[N], out[N], ti, ans[N];

int Find(int u) {
    return (u == root[u] ? u : root[u] = Find(root[u]));
}

int Union(int u, int v, int _) {
    ++n;
    root[n] = n;
    if ((u = Find(u)) == (v = Find(v))) {
        ok[n] = 1;
        g[n].push_back(u);
    } else {
        ok[n] = ok[u] | ok[v] | _;
        root[u] = root[v] = n;
        g[n].push_back(u);
        g[n].push_back(v);
    }
    return n;
}

void dfs(int u) {
    in[u] = ++ti;
    for (auto v: g[u]) {
        par[v][0] = u;
        for (int i = 1; i < 20; ++i)
            par[v][i] = par[par[v][i - 1]][i - 1];
        dfs(v);
    }
    out[u] = ti;
}

int check(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

int LCA(int u, int v) {
    if (check(u, v)) return u;
    for (int i = 19; i >= 0; --i)
        if (par[u][i] && !check(par[u][i], v)) u = par[u][i];
    return par[u][0];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    vector <tuple <int, int, int> > e;
    for (int i = 1; i <= n; ++i) root[i] = i, ok[i] = 0;
    for (int i = 0; i < M; ++i) {
        ++U[i], ++V[i];
        e.push_back({W[i], U[i], V[i]});
    }
    sort(e.begin(), e.end());
    for (int i = 0; i < e.size(); ++i) {
        auto [w, u, v] = e[i];
        ++deg[u], ++deg[v];
        int cur = Union(u, v, (deg[u] > 2 || deg[v] > 2));
        ans[cur] = w;
    }
    for (int i = n; i >= 1; --i)
        if (in[i] == 0) dfs(i);

}

int getMinimumFuelCapacity(int X, int Y) {
    ++X, ++Y;
    int w = LCA(X, Y);
    if (ok[w]) return ans[w];
    for (int i = 19; i >= 0; --i)
        if (par[w][i] && !ok[par[w][i]]) w = par[w][i];
    w = par[w][0];
    if (ok[w]) return ans[w];
    return -1;
}


#ifndef Submit

int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);

  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }

  return 0;
}

#endif // Submit

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < e.size(); ++i) {
      |                     ~~^~~~~~~~~~
swap.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |         auto [w, u, v] = e[i];
      |              ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5020 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5144 KB Output is correct
5 Correct 4 ms 5300 KB Output is correct
6 Correct 3 ms 5284 KB Output is correct
7 Correct 3 ms 5284 KB Output is correct
8 Correct 4 ms 5280 KB Output is correct
9 Correct 81 ms 25768 KB Output is correct
10 Correct 113 ms 30444 KB Output is correct
11 Correct 104 ms 30056 KB Output is correct
12 Correct 97 ms 31424 KB Output is correct
13 Correct 88 ms 33028 KB Output is correct
14 Correct 103 ms 25980 KB Output is correct
15 Correct 207 ms 36212 KB Output is correct
16 Correct 174 ms 35648 KB Output is correct
17 Correct 230 ms 37120 KB Output is correct
18 Correct 258 ms 38712 KB Output is correct
19 Correct 77 ms 14416 KB Output is correct
20 Correct 164 ms 36504 KB Output is correct
21 Correct 167 ms 35900 KB Output is correct
22 Correct 201 ms 37584 KB Output is correct
23 Correct 302 ms 39268 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5020 KB Output is correct
3 Correct 272 ms 34872 KB Output is correct
4 Correct 271 ms 39792 KB Output is correct
5 Correct 249 ms 39272 KB Output is correct
6 Correct 272 ms 39596 KB Output is correct
7 Correct 246 ms 39788 KB Output is correct
8 Correct 262 ms 38364 KB Output is correct
9 Correct 250 ms 39288 KB Output is correct
10 Correct 254 ms 38096 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5020 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5144 KB Output is correct
5 Correct 4 ms 5300 KB Output is correct
6 Correct 3 ms 5284 KB Output is correct
7 Correct 3 ms 5284 KB Output is correct
8 Correct 4 ms 5280 KB Output is correct
9 Incorrect 3 ms 4948 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 5020 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5144 KB Output is correct
5 Correct 4 ms 5300 KB Output is correct
6 Correct 3 ms 5284 KB Output is correct
7 Correct 3 ms 5284 KB Output is correct
8 Correct 4 ms 5280 KB Output is correct
9 Correct 81 ms 25768 KB Output is correct
10 Correct 113 ms 30444 KB Output is correct
11 Correct 104 ms 30056 KB Output is correct
12 Correct 97 ms 31424 KB Output is correct
13 Correct 88 ms 33028 KB Output is correct
14 Correct 103 ms 25980 KB Output is correct
15 Correct 207 ms 36212 KB Output is correct
16 Correct 174 ms 35648 KB Output is correct
17 Correct 230 ms 37120 KB Output is correct
18 Correct 258 ms 38712 KB Output is correct
19 Correct 272 ms 34872 KB Output is correct
20 Correct 271 ms 39792 KB Output is correct
21 Correct 249 ms 39272 KB Output is correct
22 Correct 272 ms 39596 KB Output is correct
23 Correct 246 ms 39788 KB Output is correct
24 Correct 262 ms 38364 KB Output is correct
25 Correct 250 ms 39288 KB Output is correct
26 Correct 254 ms 38096 KB Output is correct
27 Correct 4 ms 5204 KB Output is correct
28 Correct 4 ms 5280 KB Output is correct
29 Correct 4 ms 5280 KB Output is correct
30 Correct 4 ms 5204 KB Output is correct
31 Correct 5 ms 5288 KB Output is correct
32 Correct 4 ms 5408 KB Output is correct
33 Correct 4 ms 5320 KB Output is correct
34 Correct 4 ms 5332 KB Output is correct
35 Correct 4 ms 5332 KB Output is correct
36 Correct 13 ms 8836 KB Output is correct
37 Correct 108 ms 32448 KB Output is correct
38 Correct 104 ms 32348 KB Output is correct
39 Correct 116 ms 32416 KB Output is correct
40 Correct 109 ms 32036 KB Output is correct
41 Correct 109 ms 31952 KB Output is correct
42 Correct 100 ms 29744 KB Output is correct
43 Correct 111 ms 32404 KB Output is correct
44 Correct 107 ms 32496 KB Output is correct
45 Correct 113 ms 34488 KB Output is correct
46 Correct 111 ms 32460 KB Output is correct
47 Correct 20 ms 8844 KB Output is correct
48 Correct 194 ms 36920 KB Output is correct
49 Correct 174 ms 36928 KB Output is correct
50 Correct 192 ms 36880 KB Output is correct
51 Correct 194 ms 36644 KB Output is correct
52 Correct 183 ms 35112 KB Output is correct
53 Correct 151 ms 28836 KB Output is correct
54 Correct 195 ms 37560 KB Output is correct
55 Correct 180 ms 36908 KB Output is correct
56 Correct 255 ms 38540 KB Output is correct
57 Correct 204 ms 37644 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -