oj.uz

Submission #486620

# Submission time Handle Problem Language Result Execution time Memory
486620 2021-11-12T07:11:46 Z aryan12 Swapping Cities (APIO20_swap) C++17
0 / 100
 278 ms 58548 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
vector<array<int, 3> > edges(MAXN * 2);
int DP[20][MAXN * 3];
int depth[MAXN * 3];
vector<int> g[MAXN * 3];

struct ufds {
    bool isLine;
    pair<int, int> endpoints;
    int parent, value, depth;

    ufds(int x) {
        isLine = true;
        endpoints = {x, x};
        parent = x;
        value = 1e9;
        depth = 0;
    } 
} *Node[MAXN * 3];

int Find(int x) {
    if(Node[x]->parent == x) {
        return x;
    }
    return Node[x]->parent = Find(Node[x]->parent);
}

void Unite(int a, int b, int new_idx, int cur_val) {
    int original_a = a, original_b = b;
    a = Find(a);
    b = Find(b);
    Node[a]->parent = new_idx;
    Node[b]->parent = new_idx;
    g[new_idx].push_back(a);
    g[new_idx].push_back(b);
    Node[new_idx]->value = cur_val;
    DP[0][a] = new_idx;
    DP[0][b] = new_idx;
    if(a == b || !Node[a]->isLine || !Node[b]->isLine) {
        Node[new_idx]->isLine = false;
        Node[new_idx]->endpoints = {-1, -1};
    }
    else {
        //cout << "a = " << a << ", b = " << b << "\n";
        //cout << "A Line = " << Node[a]->endpoints.first << ", " << Node[a]->endpoints.second << "\n";
        //cout << "B Line = " << Node[b]->endpoints.first << ", " << Node[b]->endpoints.second << "\n";
        if(Node[a]->endpoints.first != original_a) {
            swap(Node[a]->endpoints.first, Node[a]->endpoints.second);
        }
        if(Node[b]->endpoints.first != original_b) {
            swap(Node[b]->endpoints.first, Node[b]->endpoints.second);
        }
        if(original_a == Node[a]->endpoints.first && original_b == Node[b]->endpoints.first) {
            Node[new_idx]->isLine = true;
            Node[new_idx]->endpoints = {Node[a]->endpoints.second, Node[b]->endpoints.second};
        }
        else {
            Node[new_idx]->isLine = false;
            Node[new_idx]->endpoints = {-1, -1};
        }
    }
}

bool cmp(array<int, 3> a, array<int, 3> b) {
    return a[2] < b[2];
}

void dfs(int node, int dep) {
    depth[node] = dep;
    for(int i = 0; i < g[node].size(); i++) {
        dfs(g[node][i], dep + 1);
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    auto begin = std::chrono::high_resolution_clock::now();
    for(int i = 0; i < 20; i++) {
        for(int j = 0; j < MAXN * 3; j++) {
            DP[i][j] = -1;
        }
    }
    for(int i = 0; i < M; i++) {
        edges[i] = {U[i], V[i], W[i]};
    }
    sort(edges.begin(), edges.begin() + M, cmp);
    int cur_new = N;
    for(int i = 0; i < MAXN * 3; i++) {
        Node[i] = new ufds(i);
    }
    for(int i = 0; i < M; i++) {
        //cout << Find(edges[i][0]) << " " << Find(edges[i][1]) << "\n"; 
        int x = Find(edges[i][0]), y = Find(edges[i][1]);
        //cout << "x = " << x << ", Node[x] is a line? " << Node[x]->isLine << "\n";
        if(x != y || Node[x]->isLine == true) {
            //cout << "Uniting edge: (" << edges[i][0] << ", " << edges[i][1] << ", " << edges[i][2] << ")\n";
            Unite(edges[i][0], edges[i][1], cur_new++, edges[i][2]);
        }
    }
    assert(cur_new <= MAXN * 3);
    for(int i = 1; i < 20; i++) {
        for(int j = 0; j < cur_new; j++) {
            if(DP[i - 1][j] != -1) {
                DP[i][j] = DP[i - 1][DP[i - 1][j]];
            }
            else {
                DP[i][j] = -1;
            }
        }
    }
    dfs(cur_new - 1, 0);
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << elapsed.count() * 1e-9 << "\n";
    if(elapsed.count() * 1e-9 > 2.0) {
        assert(false);
    }
}

bool Check(int val, int X, int Y) {
    for(int i = 19; i >= 0; i--) {
        if(DP[i][X] != -1 && Node[DP[i][X]]->value <= val) {
            X = DP[i][X];
        }
        if(DP[i][Y] != -1 && Node[DP[i][Y]]->value <= val) {
            Y = DP[i][Y];
        }
    }
    return (X == Y && Node[X]->isLine == false);
}

int lca(int X, int Y) {
    if(depth[X] < depth[Y]) {
        swap(X, Y);
    }
    int diff = depth[X] - depth[Y];
    for(int i = 19; i >= 0; i--) {
        if((1 << i) & diff) {
            X = DP[i][X];
        }
    }
    for(int i = 19; i >= 0; i--) {
        if(DP[i][X] != -1 && (DP[i][X] != DP[i][Y] || Node[DP[i][X]]->isLine)) {
            X = DP[i][X];
            Y = DP[i][Y];
        }
    }
    if(X != Y || Node[X]->isLine) {
        return -1;
    }
    return Node[X]->value;
}

int getMinimumFuelCapacity(int X, int Y) {
    return lca(X, Y);
}

Compilation message

swap.cpp: In function 'void dfs(int, int)':
swap.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 44876 KB Output is correct
2 Correct 22 ms 44844 KB Output is correct
3 Correct 21 ms 44864 KB Output is correct
4 Correct 23 ms 44892 KB Output is correct
5 Correct 24 ms 44968 KB Output is correct
6 Correct 23 ms 44996 KB Output is correct
7 Correct 23 ms 44868 KB Output is correct
8 Correct 24 ms 45012 KB Output is correct
9 Correct 96 ms 51372 KB Output is correct
10 Correct 96 ms 52548 KB Output is correct
11 Correct 94 ms 52396 KB Output is correct
12 Correct 100 ms 52768 KB Output is correct
13 Correct 88 ms 55100 KB Output is correct
14 Correct 100 ms 51480 KB Output is correct
15 Correct 180 ms 54352 KB Output is correct
16 Correct 183 ms 54188 KB Output is correct
17 Correct 221 ms 54568 KB Output is correct
18 Correct 241 ms 56876 KB Output is correct
19 Incorrect 84 ms 49860 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 44876 KB Output is correct
2 Correct 22 ms 44844 KB Output is correct
3 Incorrect 278 ms 58548 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 44876 KB Output is correct
2 Correct 22 ms 44844 KB Output is correct
3 Correct 21 ms 44864 KB Output is correct
4 Correct 23 ms 44892 KB Output is correct
5 Correct 24 ms 44968 KB Output is correct
6 Correct 23 ms 44996 KB Output is correct
7 Correct 23 ms 44868 KB Output is correct
8 Correct 24 ms 45012 KB Output is correct
9 Incorrect 21 ms 44876 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 44876 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 44876 KB Output is correct
2 Correct 22 ms 44844 KB Output is correct
3 Correct 21 ms 44864 KB Output is correct
4 Correct 23 ms 44892 KB Output is correct
5 Correct 24 ms 44968 KB Output is correct
6 Correct 23 ms 44996 KB Output is correct
7 Correct 23 ms 44868 KB Output is correct
8 Correct 24 ms 45012 KB Output is correct
9 Correct 96 ms 51372 KB Output is correct
10 Correct 96 ms 52548 KB Output is correct
11 Correct 94 ms 52396 KB Output is correct
12 Correct 100 ms 52768 KB Output is correct
13 Correct 88 ms 55100 KB Output is correct
14 Correct 100 ms 51480 KB Output is correct
15 Correct 180 ms 54352 KB Output is correct
16 Correct 183 ms 54188 KB Output is correct
17 Correct 221 ms 54568 KB Output is correct
18 Correct 241 ms 56876 KB Output is correct
19 Incorrect 278 ms 58548 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 44876 KB Output isn't correct