oj.uz

Submission #758423

# Submission time Handle Problem Language Result Execution time Memory
758423 2023-06-14T15:25:00 Z yellowtoad Swapping Cities (APIO20_swap) C++17
13 / 100
 468 ms 57928 KB 
#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
#define int long long
using namespace std;

int n, m, freq[100010], p[100010], id[100010], par[300010][20], depth[300010];
bool can[300010];
pair<int,pair<int,int>> ed[200010];
vector<int> edge[300010];

int dsu(int u) {
    if (p[u] == u) return u;
    return (p[u] = dsu(p[u]));
}

void dfs(int u, int d) {
    int v = par[u][0];
    depth[u] = d;
    for (int i = 1; i <= 19; i++) {
        if (v == -1) {
            par[u][i] = -1;
            continue;
        }
        par[u][i] = par[v][i-1];
        v = par[u][i];
    }
    for (int i = 0; i < edge[u].size(); i++) dfs(edge[u][i],d+1);
}

int lca(int u, int v) {
    if (depth[v] < depth[u]) swap(u,v);
    int i = 19;
    while (depth[v] != depth[u]) {
        if ((par[v][i] != -1) && (depth[par[v][i]] >= depth[u])) v = par[v][i];
        i--;
    }
    if (v == u) return u;
    while (i >= 0) {
        if (par[v][i] != par[u][i]) {
            u = par[u][i];
            v = par[v][i];
        }
        i--;
    }
    return par[u][0];
}

void init(signed N, signed M, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
    n = N; m = M;
    for (int i = 0; i < m; i++) ed[i] = {W[i],{U[i],V[i]}};
    sort(ed,ed+m);
    for (int i = 0; i < n; i++) p[i] = id[i] = i;
    for (int i = 0; i < m; i++) {
        int u = ed[i].s.f, v = ed[i].s.s, w = ed[i].f;
        if (dsu(u) == dsu(v)) {
            par[id[dsu(u)]][0] = n+i;
            edge[n+i].push_back(id[dsu(u)]);
            id[dsu(u)] = n+i;
            freq[u]++;
            freq[v]++;
            can[n+i] = 1;
        } else {
            par[id[dsu(u)]][0] = n+i;
            par[id[dsu(v)]][0] = n+i;
            edge[n+i].push_back(id[dsu(u)]);
            edge[n+i].push_back(id[dsu(v)]);
            freq[u]++;
            freq[v]++;
            if ((freq[u] >= 3) || (freq[v] >= 3) || (can[id[dsu(u)]]) || (can[id[dsu(v)]])) can[n+i] = 1;
            p[dsu(v)] = p[dsu(u)];
            id[dsu(u)] = n+i;
        }
    }
    for (int i = 0; i <= 19; i++) par[n+m-1][i] = -1;
    dfs(n+m-1,1);
    /*for (int i = 0; i < n+m; i++) {
        for (int j = 0; j <= 19; j++) cout << par[i][j] << " ";
        cout << endl;
    }*/
}

signed getMinimumFuelCapacity(signed U, signed V) {
    int u = lca(U,V);
    if (can[u]) return ed[u-n].f;
    int i = 19;
    while (i >= 0) {
        if ((par[u][i] != -1) && (!can[par[u][i]])) u = par[u][i];
        i--;
    }
    if (par[u][0] == -1) return -1;
    return ed[par[u][0]-n].f;
}

Compilation message

swap.cpp: In function 'void dfs(long long int, long long int)':
swap.cpp:31:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < edge[u].size(); i++) dfs(edge[u][i],d+1);
      |                     ~~^~~~~~~~~~~~~~~~
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:58:43: warning: unused variable 'w' [-Wunused-variable]
   58 |         int u = ed[i].s.f, v = ed[i].s.s, w = ed[i].f;
      |                                           ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7384 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 5 ms 7764 KB Output is correct
6 Correct 4 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 4 ms 7764 KB Output is correct
9 Correct 92 ms 41084 KB Output is correct
10 Correct 113 ms 48668 KB Output is correct
11 Correct 116 ms 48020 KB Output is correct
12 Correct 116 ms 50416 KB Output is correct
13 Correct 143 ms 52760 KB Output is correct
14 Correct 108 ms 41168 KB Output is correct
15 Correct 258 ms 50772 KB Output is correct
16 Correct 256 ms 49588 KB Output is correct
17 Correct 253 ms 52176 KB Output is correct
18 Correct 441 ms 54496 KB Output is correct
19 Correct 80 ms 17664 KB Output is correct
20 Correct 262 ms 52104 KB Output is correct
21 Correct 240 ms 50696 KB Output is correct
22 Correct 247 ms 53592 KB Output is correct
23 Correct 468 ms 55840 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7384 KB Output is correct
3 Correct 338 ms 55660 KB Output is correct
4 Correct 325 ms 57928 KB Output is correct
5 Correct 364 ms 56492 KB Output is correct
6 Correct 339 ms 57648 KB Output is correct
7 Correct 349 ms 57272 KB Output is correct
8 Correct 338 ms 55284 KB Output is correct
9 Correct 350 ms 56816 KB Output is correct
10 Correct 331 ms 54836 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7384 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 5 ms 7764 KB Output is correct
6 Correct 4 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 4 ms 7764 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Incorrect 5 ms 7736 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7384 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 5 ms 7764 KB Output is correct
9 Correct 4 ms 7764 KB Output is correct
10 Correct 92 ms 41084 KB Output is correct
11 Correct 113 ms 48668 KB Output is correct
12 Correct 116 ms 48020 KB Output is correct
13 Correct 116 ms 50416 KB Output is correct
14 Correct 143 ms 52760 KB Output is correct
15 Incorrect 5 ms 7736 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7384 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 5 ms 7764 KB Output is correct
6 Correct 4 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 4 ms 7764 KB Output is correct
9 Correct 92 ms 41084 KB Output is correct
10 Correct 113 ms 48668 KB Output is correct
11 Correct 116 ms 48020 KB Output is correct
12 Correct 116 ms 50416 KB Output is correct
13 Correct 143 ms 52760 KB Output is correct
14 Correct 108 ms 41168 KB Output is correct
15 Correct 258 ms 50772 KB Output is correct
16 Correct 256 ms 49588 KB Output is correct
17 Correct 253 ms 52176 KB Output is correct
18 Correct 441 ms 54496 KB Output is correct
19 Correct 338 ms 55660 KB Output is correct
20 Correct 325 ms 57928 KB Output is correct
21 Correct 364 ms 56492 KB Output is correct
22 Correct 339 ms 57648 KB Output is correct
23 Correct 349 ms 57272 KB Output is correct
24 Correct 338 ms 55284 KB Output is correct
25 Correct 350 ms 56816 KB Output is correct
26 Correct 331 ms 54836 KB Output is correct
27 Incorrect 5 ms 7736 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 4 ms 7384 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 4 ms 7764 KB Output is correct
8 Correct 5 ms 7764 KB Output is correct
9 Correct 4 ms 7764 KB Output is correct
10 Correct 92 ms 41084 KB Output is correct
11 Correct 113 ms 48668 KB Output is correct
12 Correct 116 ms 48020 KB Output is correct
13 Correct 116 ms 50416 KB Output is correct
14 Correct 143 ms 52760 KB Output is correct
15 Correct 108 ms 41168 KB Output is correct
16 Correct 258 ms 50772 KB Output is correct
17 Correct 256 ms 49588 KB Output is correct
18 Correct 253 ms 52176 KB Output is correct
19 Correct 441 ms 54496 KB Output is correct
20 Correct 338 ms 55660 KB Output is correct
21 Correct 325 ms 57928 KB Output is correct
22 Correct 364 ms 56492 KB Output is correct
23 Correct 339 ms 57648 KB Output is correct
24 Correct 349 ms 57272 KB Output is correct
25 Correct 338 ms 55284 KB Output is correct
26 Correct 350 ms 56816 KB Output is correct
27 Correct 331 ms 54836 KB Output is correct
28 Incorrect 5 ms 7736 KB Output isn't correct
29 Halted 0 ms 0 KB -