oj.uz

답안 #972820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972820 2024-05-01T08:27:16 Z DAleksa 자매 도시 (APIO20_swap) C++17
0 / 100
 464 ms 524288 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

int tsz;

struct DSU {
    int n;
    vector<int> parent, sz;
    vector<bool> chain;
    vector<vector<int>> comp;
    vector<int> id;
    DSU(int _n) {
        n = _n;
        parent.resize(n);
        sz.resize(n);
        comp.resize(n);
        chain.resize(n);
        id.resize(n);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
            sz[i] = 1;
            chain[i] = true;
            comp[i].push_back(i);
            id[i] = i;
        }
    }
    int find_parent(int u) {
        if(parent[u] == u) return u;
        return parent[u] = find_parent(parent[u]);
    }
    bool check(int u, int v) {
        u = find_parent(u);
        v = find_parent(v);
        return u == v;
    }
    void join(int u, int v) {
        u = find_parent(u);
        v = find_parent(v);
        if(sz[u] > sz[v]) swap(u, v);
        for(int i : comp[u]) comp[v].push_back(i);
        comp[u].clear();
        parent[u] = v;
        id[v] = tsz;
    }
    void update_chain_state(int u) {
        u = find_parent(u);
        chain[u] = false;
    }
    int get_size(int u) {
        u = find_parent(u);
        return sz[u];
    }
};

const int N = 1e6 + 10, LOG = 20;
bool leaf[N];
DSU dsu(N), tree(2 * N);
int order[N];
vector<int> g[2 * N];
int up[2 * N][LOG + 1];
int root;
int timer;
int tin[2 * N], tout[2 * N];
int ans[2 * N];
bool mark[2 * N];

void dfs(int u, int par) {
    mark[u] = true;
    tin[u] = ++timer;
    for(int v : g[u]) {
        dfs(v, u);
        up[v][0] = u;
    }
    tout[u] = ++timer;
}

bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int LCA(int u, int v) {
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j = LOG - 1; j >= 0; j--) {
        if(up[u][j] == 0) continue;
        if(is_ancestor(up[u][j], v)) continue;
        u = up[u][j];
    }
    return up[u][0];
}

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    for(int i = 0; i < N; i++) leaf[i] = true;
    tsz = n;
    for(int i = 0; i < m; i++) order[i] = i;
    sort(order, order + m, [&](int i, int j) { return W[i] < W[j]; });
    for(int i = 0; i < m; i++) {
        int u = U[order[i]], v = V[order[i]];
        if(dsu.check(u, v)) {
            int par = dsu.find_parent(u);
            if(dsu.chain[par]) {
                for(int j : dsu.comp[par]) {
                    g[tsz].push_back(j);
                    tree.join(tsz, j);
                }
                ans[tsz] = W[order[i]];
                tsz++;
                dsu.update_chain_state(par);
            }
        } else {
            if(!dsu.chain[dsu.find_parent(u)] || !dsu.chain[dsu.find_parent(v)]) {
                if(dsu.chain[dsu.find_parent(u)]) {
                    for(int j : dsu.comp[dsu.find_parent(u)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                } else {
                    g[tsz].push_back(dsu.id[dsu.find_parent(u)]);
                    tree.join(tsz, dsu.id[dsu.find_parent(u)]);
                }
                if(dsu.chain[dsu.find_parent(v)]) {
                    for(int j : dsu.comp[dsu.find_parent(v)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                } else {
                    g[tsz].push_back(dsu.id[dsu.find_parent(v)]);
                    tree.join(tsz, dsu.id[dsu.find_parent(v)]);
                }
                dsu.join(u, v);
                ans[tsz] = W[order[i]];
                tsz++;
            } else {
                if(leaf[u] && leaf[v]) {
                    if(dsu.get_size(u) > 1) leaf[u] = false;
                    if(dsu.get_size(v) > 1) leaf[v] = false;
                    dsu.join(u, v);
                } else {
                    for(int j : dsu.comp[dsu.find_parent(u)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                    for(int j : dsu.comp[dsu.find_parent(v)]) {
                        g[tsz].push_back(j);
                        tree.join(tsz, j);
                    }
                    dsu.join(u, v);
                    ans[tsz] = W[order[i]];
                    tsz++;
                    dsu.update_chain_state(u);
                }
            }
        }
    }
//    for(int i = 0; i < tsz; i++) {
//        cout << i << ": ";
//        for(int j : g[i]) cout << j << " ";
//        cout << "\n";
//    }
    root = tsz - 1;
    for(int i = root; i >= 0; i--) if(!mark[i]) dfs(i, -1);
    for(int j = 1; j < LOG; j++) for(int i = 0; i <= root; i++) up[i][j] = up[up[i][j - 1]][j - 1];
}

int getMinimumFuelCapacity(int X, int Y) {
    if(!tree.check(X, Y)) return -1;
    return ans[LCA(X, Y)];
}

/*

5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1




*/

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 183 ms 248260 KB Output is correct
4 Correct 183 ms 248400 KB Output is correct
5 Correct 181 ms 248344 KB Output is correct
6 Correct 186 ms 248400 KB Output is correct
7 Correct 186 ms 248372 KB Output is correct
8 Correct 192 ms 249424 KB Output is correct
9 Correct 240 ms 262408 KB Output is correct
10 Correct 245 ms 265780 KB Output is correct
11 Correct 248 ms 265504 KB Output is correct
12 Correct 251 ms 266828 KB Output is correct
13 Runtime error 463 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Runtime error 464 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 183 ms 248260 KB Output is correct
4 Correct 183 ms 248400 KB Output is correct
5 Correct 181 ms 248344 KB Output is correct
6 Correct 186 ms 248400 KB Output is correct
7 Correct 186 ms 248372 KB Output is correct
8 Correct 192 ms 249424 KB Output is correct
9 Correct 190 ms 248280 KB Output is correct
10 Incorrect 186 ms 248656 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 248280 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 187 ms 248400 KB Output is correct
4 Correct 183 ms 248260 KB Output is correct
5 Correct 183 ms 248400 KB Output is correct
6 Correct 181 ms 248344 KB Output is correct
7 Correct 186 ms 248400 KB Output is correct
8 Correct 186 ms 248372 KB Output is correct
9 Correct 192 ms 249424 KB Output is correct
10 Correct 240 ms 262408 KB Output is correct
11 Correct 245 ms 265780 KB Output is correct
12 Correct 248 ms 265504 KB Output is correct
13 Correct 251 ms 266828 KB Output is correct
14 Runtime error 463 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 248400 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 183 ms 248260 KB Output is correct
4 Correct 183 ms 248400 KB Output is correct
5 Correct 181 ms 248344 KB Output is correct
6 Correct 186 ms 248400 KB Output is correct
7 Correct 186 ms 248372 KB Output is correct
8 Correct 192 ms 249424 KB Output is correct
9 Correct 240 ms 262408 KB Output is correct
10 Correct 245 ms 265780 KB Output is correct
11 Correct 248 ms 265504 KB Output is correct
12 Correct 251 ms 266828 KB Output is correct
13 Runtime error 463 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 248280 KB Output is correct
2 Correct 187 ms 248400 KB Output is correct
3 Correct 187 ms 248400 KB Output is correct
4 Correct 183 ms 248260 KB Output is correct
5 Correct 183 ms 248400 KB Output is correct
6 Correct 181 ms 248344 KB Output is correct
7 Correct 186 ms 248400 KB Output is correct
8 Correct 186 ms 248372 KB Output is correct
9 Correct 192 ms 249424 KB Output is correct
10 Correct 240 ms 262408 KB Output is correct
11 Correct 245 ms 265780 KB Output is correct
12 Correct 248 ms 265504 KB Output is correct
13 Correct 251 ms 266828 KB Output is correct
14 Runtime error 463 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -