oj.uz

Submission #558025

# Submission time Handle Problem Language Result Execution time Memory
558025 2022-05-06T14:00:49 Z InternetPerson10 Swapping Cities (APIO20_swap) C++17
13 / 100
 474 ms 48424 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

int BIG = 1e9 + 7; // 
int second[100001];
int third[100001];
int depth[100001];
int parent[100001];
int parWeight[100001];
int liftWt[100001][20]; // The maximum of weights when going above
int liftVal[100001][20]; // The vertex that is 2^i above
int liftMin[100001][20]; // The minimum of the thirds up to 2^i above

vector<vector<pair<int, int>>> adj;

void dfs(int n, int par = -1) {
    for(auto p : adj[n]) {
        int ch, w;
        tie(ch, w) = p;
        if(ch == par) continue;
        parWeight[ch] = w;
        parent[ch] = n;
        depth[ch] = depth[n] + 1;
        dfs(ch, n);
    }
}

struct dsu {
    vector<int> par, siz, lin, linen;
    void init(int n) {
        par.resize(n);
        siz.resize(n, 1);
        lin.resize(n, BIG);
        linen.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(par[x] == x) return x;
        int g = get(par[x]);
        if(lin[x] != BIG) return par[x] = g;
        if(lin[par[x]] != BIG) {
            lin[x] = lin[par[x]];
            linen[x] = 0;
        }
        return par[x] = g;
    }
    bool unite(int x, int y, int w) {
        int gx = get(x), gy = get(y);
        if(gx == gy) {
            if(lin[gx] == BIG) {
                lin[gx] = w;
                linen[gx] = 0;
            }
            return false;
        }
        // Connecting a line and a line, becomes a line
        if(lin[gx] == BIG && lin[gy] == BIG && linen[x] && linen[y]) {
            if(siz[x] != 1) linen[x] = 0;
            if(siz[y] != 1) linen[y] = 0;
        }
        // Connecting a line and a line, doesn't become a line
        else {
            lin[gx] = min(lin[gx], w);
            lin[gy] = min(lin[gy], w);
            linen[x] = linen[y] = 0;
        }
        x = gx; y = gy;
        if(siz[x] > siz[y]) swap(x, y);
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

dsu uf;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    vector<pair<int, pair<int, int>>> edges(M);
    for(int i = 0; i < N; i++) {
        depth[i] = 0;
        second[i] = BIG;
        third[i] = -1;
        parent[i] = 0;
    }
    adj.resize(N);
    for(int i = 0; i < M; i++) {
        edges[i] = {W[i], {U[i], V[i]}};
    }
    sort(edges.begin(), edges.end());
    uf.init(N);
    for(auto [w, p] : edges) {
        int u, v;
        tie(u, v) = p;
        if(third[u] < 0) {
            third[u]--;
            if(third[u] == -3) second[u] = w;
            if(third[u] == -4) third[u] = w;
        }
        if(third[v] < 0) {
            third[v]--;
            if(third[v] == -3) second[v] = w;
            if(third[v] == -4) third[v] = w;
        }
        if(uf.unite(u, v, w)) {
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }
    for(int i = 0; i < N; i++) {
        uf.get(i);
        if(third[i] < 0) third[i] = BIG;
    }
    dfs(0);
    for(int i = 0; i < 20; i++) {
        liftWt[0][i] = liftVal[0][i] = 0;
        liftMin[0][i] = third[0];
    }
    for(int x = 1; x < N; x++) {
        liftWt[x][0] = parWeight[x];
        liftVal[x][0] = parent[x];
        liftMin[x][0] = min(third[x], third[parent[x]]);
    }
    for(int i = 1; i < 20; i++) {
        for(int x = 1; x < N; x++) {
            int xUp = liftVal[x][i-1];
            liftWt[x][i] = max(liftWt[x][i-1], liftWt[xUp][i-1]);
            liftVal[x][i] = liftVal[xUp][i-1];
            liftMin[x][i] = min(liftMin[x][i-1], liftMin[xUp][i-1]);
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    int weightMax = 0, thirdMin = BIG;
    int secondx = uf.lin[x], secondy = uf.lin[y];
    if(depth[x] > depth[y]) swap(x, y);
    if(depth[x] < depth[y]) {
        int g = depth[y] - depth[x];
        for(int i = 0; i < 20; i++) {
            if(g & (1 << i)) {
                weightMax = max(weightMax, liftWt[y][i]);
                thirdMin = min(thirdMin, liftMin[y][i]);
                y = liftVal[y][i];
            }
        }
    }
    for(int i = 19; i >= 0; i--) {
        if(liftVal[x][i] != liftVal[y][i]) {
            weightMax = max(weightMax, liftWt[x][i]);
            thirdMin = min(thirdMin, liftMin[x][i]);
            x = liftVal[x][i];
            weightMax = max(weightMax, liftWt[y][i]);
            thirdMin = min(thirdMin, liftMin[y][i]);
            y = liftVal[y][i];
        }
        if(i == 0 && x != y) {
            weightMax = max(weightMax, liftWt[x][i]);
            thirdMin = min(thirdMin, liftMin[x][i]);
            x = liftVal[x][i];
            weightMax = max(weightMax, liftWt[y][i]);
            thirdMin = min(thirdMin, liftMin[y][i]);
            y = liftVal[y][i];
        }
    }
    int ans = max(weightMax, min(thirdMin, min(secondx, secondy)));
    if(ans == BIG) return -1;
    return ans;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 176 ms 33208 KB Output is correct
10 Correct 227 ms 41656 KB Output is correct
11 Correct 150 ms 40524 KB Output is correct
12 Correct 173 ms 43176 KB Output is correct
13 Correct 164 ms 44548 KB Output is correct
14 Correct 150 ms 32892 KB Output is correct
15 Correct 428 ms 45624 KB Output is correct
16 Correct 378 ms 43084 KB Output is correct
17 Correct 434 ms 48424 KB Output is correct
18 Correct 362 ms 47340 KB Output is correct
19 Correct 93 ms 12176 KB Output is correct
20 Correct 380 ms 45268 KB Output is correct
21 Correct 412 ms 43352 KB Output is correct
22 Correct 474 ms 46972 KB Output is correct
23 Correct 400 ms 47400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 190 ms 40792 KB Output is correct
4 Correct 182 ms 42500 KB Output is correct
5 Correct 189 ms 41708 KB Output is correct
6 Correct 186 ms 42272 KB Output is correct
7 Correct 183 ms 42176 KB Output is correct
8 Correct 183 ms 40752 KB Output is correct
9 Correct 181 ms 41752 KB Output is correct
10 Correct 206 ms 40344 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 1 ms 704 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 580 KB Output is correct
15 Correct 1 ms 704 KB Output is correct
16 Incorrect 2 ms 724 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 176 ms 33208 KB Output is correct
11 Correct 227 ms 41656 KB Output is correct
12 Correct 150 ms 40524 KB Output is correct
13 Correct 173 ms 43176 KB Output is correct
14 Correct 164 ms 44548 KB Output is correct
15 Correct 2 ms 704 KB Output is correct
16 Correct 1 ms 704 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 580 KB Output is correct
20 Correct 1 ms 704 KB Output is correct
21 Incorrect 2 ms 724 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 692 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 176 ms 33208 KB Output is correct
10 Correct 227 ms 41656 KB Output is correct
11 Correct 150 ms 40524 KB Output is correct
12 Correct 173 ms 43176 KB Output is correct
13 Correct 164 ms 44548 KB Output is correct
14 Correct 150 ms 32892 KB Output is correct
15 Correct 428 ms 45624 KB Output is correct
16 Correct 378 ms 43084 KB Output is correct
17 Correct 434 ms 48424 KB Output is correct
18 Correct 362 ms 47340 KB Output is correct
19 Correct 190 ms 40792 KB Output is correct
20 Correct 182 ms 42500 KB Output is correct
21 Correct 189 ms 41708 KB Output is correct
22 Correct 186 ms 42272 KB Output is correct
23 Correct 183 ms 42176 KB Output is correct
24 Correct 183 ms 40752 KB Output is correct
25 Correct 181 ms 41752 KB Output is correct
26 Correct 206 ms 40344 KB Output is correct
27 Correct 2 ms 704 KB Output is correct
28 Correct 1 ms 704 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 580 KB Output is correct
32 Correct 1 ms 704 KB Output is correct
33 Incorrect 2 ms 724 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 176 ms 33208 KB Output is correct
11 Correct 227 ms 41656 KB Output is correct
12 Correct 150 ms 40524 KB Output is correct
13 Correct 173 ms 43176 KB Output is correct
14 Correct 164 ms 44548 KB Output is correct
15 Correct 150 ms 32892 KB Output is correct
16 Correct 428 ms 45624 KB Output is correct
17 Correct 378 ms 43084 KB Output is correct
18 Correct 434 ms 48424 KB Output is correct
19 Correct 362 ms 47340 KB Output is correct
20 Correct 190 ms 40792 KB Output is correct
21 Correct 182 ms 42500 KB Output is correct
22 Correct 189 ms 41708 KB Output is correct
23 Correct 186 ms 42272 KB Output is correct
24 Correct 183 ms 42176 KB Output is correct
25 Correct 183 ms 40752 KB Output is correct
26 Correct 181 ms 41752 KB Output is correct
27 Correct 206 ms 40344 KB Output is correct
28 Correct 2 ms 704 KB Output is correct
29 Correct 1 ms 704 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 1 ms 580 KB Output is correct
33 Correct 1 ms 704 KB Output is correct
34 Incorrect 2 ms 724 KB Output isn't correct
35 Halted 0 ms 0 KB -