oj.uz

Submission #758415

# Submission time Handle Problem Language Result Execution time Memory
758415 2023-06-14T15:19:34 Z yellowtoad Swapping Cities (APIO20_swap) C++17
13 / 100
 358 ms 43016 KB 
#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
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(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> 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;
    }*/
}

int getMinimumFuelCapacity(int U, int 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(int, int)':
swap.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     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:57:43: warning: unused variable 'w' [-Wunused-variable]
   57 |         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 4 ms 7380 KB Output is correct
2 Correct 5 ms 7352 KB Output is correct
3 Correct 5 ms 7352 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7516 KB Output is correct
6 Correct 4 ms 7496 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7624 KB Output is correct
9 Correct 83 ms 27976 KB Output is correct
10 Correct 95 ms 32616 KB Output is correct
11 Correct 97 ms 32192 KB Output is correct
12 Correct 107 ms 33720 KB Output is correct
13 Correct 108 ms 36120 KB Output is correct
14 Correct 91 ms 28352 KB Output is correct
15 Correct 225 ms 37036 KB Output is correct
16 Correct 212 ms 36200 KB Output is correct
17 Correct 227 ms 37740 KB Output is correct
18 Correct 332 ms 40116 KB Output is correct
19 Correct 78 ms 16668 KB Output is correct
20 Correct 212 ms 38088 KB Output is correct
21 Correct 221 ms 37428 KB Output is correct
22 Correct 235 ms 39248 KB Output is correct
23 Correct 358 ms 41524 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7352 KB Output is correct
3 Correct 257 ms 37928 KB Output is correct
4 Correct 293 ms 43016 KB Output is correct
5 Correct 263 ms 42468 KB Output is correct
6 Correct 271 ms 42936 KB Output is correct
7 Correct 260 ms 42792 KB Output is correct
8 Correct 262 ms 41528 KB Output is correct
9 Correct 252 ms 42480 KB Output is correct
10 Correct 255 ms 41380 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7352 KB Output is correct
3 Correct 5 ms 7352 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7516 KB Output is correct
6 Correct 4 ms 7496 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7624 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Incorrect 5 ms 7636 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 4 ms 7380 KB Output is correct
3 Correct 5 ms 7352 KB Output is correct
4 Correct 5 ms 7352 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 4 ms 7496 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 5 ms 7624 KB Output is correct
10 Correct 83 ms 27976 KB Output is correct
11 Correct 95 ms 32616 KB Output is correct
12 Correct 97 ms 32192 KB Output is correct
13 Correct 107 ms 33720 KB Output is correct
14 Correct 108 ms 36120 KB Output is correct
15 Incorrect 5 ms 7636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7352 KB Output is correct
3 Correct 5 ms 7352 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7516 KB Output is correct
6 Correct 4 ms 7496 KB Output is correct
7 Correct 5 ms 7636 KB Output is correct
8 Correct 5 ms 7624 KB Output is correct
9 Correct 83 ms 27976 KB Output is correct
10 Correct 95 ms 32616 KB Output is correct
11 Correct 97 ms 32192 KB Output is correct
12 Correct 107 ms 33720 KB Output is correct
13 Correct 108 ms 36120 KB Output is correct
14 Correct 91 ms 28352 KB Output is correct
15 Correct 225 ms 37036 KB Output is correct
16 Correct 212 ms 36200 KB Output is correct
17 Correct 227 ms 37740 KB Output is correct
18 Correct 332 ms 40116 KB Output is correct
19 Correct 257 ms 37928 KB Output is correct
20 Correct 293 ms 43016 KB Output is correct
21 Correct 263 ms 42468 KB Output is correct
22 Correct 271 ms 42936 KB Output is correct
23 Correct 260 ms 42792 KB Output is correct
24 Correct 262 ms 41528 KB Output is correct
25 Correct 252 ms 42480 KB Output is correct
26 Correct 255 ms 41380 KB Output is correct
27 Incorrect 5 ms 7636 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 4 ms 7380 KB Output is correct
3 Correct 5 ms 7352 KB Output is correct
4 Correct 5 ms 7352 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct
7 Correct 4 ms 7496 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct
9 Correct 5 ms 7624 KB Output is correct
10 Correct 83 ms 27976 KB Output is correct
11 Correct 95 ms 32616 KB Output is correct
12 Correct 97 ms 32192 KB Output is correct
13 Correct 107 ms 33720 KB Output is correct
14 Correct 108 ms 36120 KB Output is correct
15 Correct 91 ms 28352 KB Output is correct
16 Correct 225 ms 37036 KB Output is correct
17 Correct 212 ms 36200 KB Output is correct
18 Correct 227 ms 37740 KB Output is correct
19 Correct 332 ms 40116 KB Output is correct
20 Correct 257 ms 37928 KB Output is correct
21 Correct 293 ms 43016 KB Output is correct
22 Correct 263 ms 42468 KB Output is correct
23 Correct 271 ms 42936 KB Output is correct
24 Correct 260 ms 42792 KB Output is correct
25 Correct 262 ms 41528 KB Output is correct
26 Correct 252 ms 42480 KB Output is correct
27 Correct 255 ms 41380 KB Output is correct
28 Incorrect 5 ms 7636 KB Output isn't correct
29 Halted 0 ms 0 KB -