oj.uz

답안 #972818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972818 2024-05-01T08:25:33 Z DAleksa 자매 도시 (APIO20_swap) C++17
0 / 100
 664 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 = 1e5 + 10, LOG = 17;
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 38 ms 29256 KB Output is correct
2 Correct 17 ms 29276 KB Output is correct
3 Correct 21 ms 29280 KB Output is correct
4 Correct 18 ms 29276 KB Output is correct
5 Correct 21 ms 29276 KB Output is correct
6 Correct 18 ms 29420 KB Output is correct
7 Correct 19 ms 29272 KB Output is correct
8 Correct 20 ms 30040 KB Output is correct
9 Correct 72 ms 41836 KB Output is correct
10 Correct 76 ms 45168 KB Output is correct
11 Correct 75 ms 44952 KB Output is correct
12 Correct 77 ms 46396 KB Output is correct
13 Runtime error 664 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 29256 KB Output is correct
2 Correct 17 ms 29276 KB Output is correct
3 Correct 21 ms 29280 KB Output is correct
4 Correct 18 ms 29276 KB Output is correct
5 Correct 21 ms 29276 KB Output is correct
6 Correct 18 ms 29420 KB Output is correct
7 Correct 19 ms 29272 KB Output is correct
8 Correct 20 ms 30040 KB Output is correct
9 Correct 18 ms 29320 KB Output is correct
10 Incorrect 23 ms 29532 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 29320 KB Output is correct
2 Correct 38 ms 29256 KB Output is correct
3 Correct 17 ms 29276 KB Output is correct
4 Correct 21 ms 29280 KB Output is correct
5 Correct 18 ms 29276 KB Output is correct
6 Correct 21 ms 29276 KB Output is correct
7 Correct 18 ms 29420 KB Output is correct
8 Correct 19 ms 29272 KB Output is correct
9 Correct 20 ms 30040 KB Output is correct
10 Correct 72 ms 41836 KB Output is correct
11 Correct 76 ms 45168 KB Output is correct
12 Correct 75 ms 44952 KB Output is correct
13 Correct 77 ms 46396 KB Output is correct
14 Runtime error 664 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 29256 KB Output is correct
2 Correct 17 ms 29276 KB Output is correct
3 Correct 21 ms 29280 KB Output is correct
4 Correct 18 ms 29276 KB Output is correct
5 Correct 21 ms 29276 KB Output is correct
6 Correct 18 ms 29420 KB Output is correct
7 Correct 19 ms 29272 KB Output is correct
8 Correct 20 ms 30040 KB Output is correct
9 Correct 72 ms 41836 KB Output is correct
10 Correct 76 ms 45168 KB Output is correct
11 Correct 75 ms 44952 KB Output is correct
12 Correct 77 ms 46396 KB Output is correct
13 Runtime error 664 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 29320 KB Output is correct
2 Correct 38 ms 29256 KB Output is correct
3 Correct 17 ms 29276 KB Output is correct
4 Correct 21 ms 29280 KB Output is correct
5 Correct 18 ms 29276 KB Output is correct
6 Correct 21 ms 29276 KB Output is correct
7 Correct 18 ms 29420 KB Output is correct
8 Correct 19 ms 29272 KB Output is correct
9 Correct 20 ms 30040 KB Output is correct
10 Correct 72 ms 41836 KB Output is correct
11 Correct 76 ms 45168 KB Output is correct
12 Correct 75 ms 44952 KB Output is correct
13 Correct 77 ms 46396 KB Output is correct
14 Runtime error 664 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -