oj.uz

답안 #251210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251210 2020-07-20T15:25:09 Z Sorting Pipes (CEOI15_pipes) C++14
50 / 100
 4923 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_M = 6e6 + 3;
const int k_N = 1e5 + 3;
const int k_LOG_N = 20;

int n, m;
vector<pair<int, int>> adj[k_N];

vector<pair<int, int>> edges;

int p[k_N], sz[k_N], root[k_N], suffix[k_N];
int up[k_LOG_N][k_N], d[k_N];

bool not_critical[k_N];

int find_p(int x){
    if(x == p[x]) return x;
    return p[x] = find_p(p[x]);
}

int dfs(int x, int parent = -1){
    int sum = 0;
    for(auto [to, idx]: adj[x]){
        if(to == parent) continue;

        int curr = dfs(to, x);
        if(curr) not_critical[idx] = true;
        sum += curr;
    }

    return sum += suffix[x];
}

void dfs_join(int x, int parent){
    up[0][x] = parent;
    d[x] = d[parent] + 1;

    for(int i = 1; i < k_LOG_N; ++i)
        up[i][x] = up[i - 1][up[i - 1][x]];

    for(auto [to, idx]: adj[x]){
        if(to == parent) continue;
        dfs_join(to, x);
    }
}

bool unite(int x, int y){
    if(find_p(x) == find_p(y)) return false;
    if(sz[p[x]] < sz[p[y]]) swap(x, y);

    dfs(root[p[y]]);
    dfs_join(y, x);

    sz[p[x]] += sz[p[y]];
    p[p[y]] = p[x];
    return true;
}

int get_lca(int u, int v){
    if(d[u] < d[v]) swap(u, v);

    int diff = d[u] - d[v];
    if(diff){
        for(int i = k_LOG_N - 1; i >= 0; --i){
            if(diff & (1 << i)){
                u = up[i][u];
            }
        }
    }

    if(u == v) return u;

    for(int i = k_LOG_N - 1; i >= 0; --i){
        if(up[i][u] != up[i][v]){
            u = up[i][u];
            v = up[i][v];
        }
    }

    return up[0][u];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for(int i = 1; i <= n; ++i){
        p[i] = i;
        sz[i] = 1;
        root[i] = i;
        suffix[i] = 0;
        d[i] = 0;

        //for(int j = 0; j < k_LOG_N; ++j)
        //    up[j][i] = i;
    }

    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;

        if(unite(u, v)){
            edges.push_back({u, v});
            adj[u].push_back({v, edges.size() - 1});
            adj[v].push_back({u, edges.size() - 1});
        }
        else{
            int lca = get_lca(u, v);
            suffix[lca] -= 2;
            suffix[u]++;
            suffix[v]++;
        }
    }

    for(int i = 1; i <= n; ++i)
        if(i == find_p(i))
            dfs(root[i]);

    for(int i = 0; i < edges.size(); ++i)
        if(!not_critical[i])
            cout << edges[i].first << " " << edges[i].second << "\n";
}

Compilation message

pipes.cpp: In function 'int dfs(int, int)':
pipes.cpp:26:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [to, idx]: adj[x]){
              ^
pipes.cpp: In function 'void dfs_join(int, int)':
pipes.cpp:44:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [to, idx]: adj[x]){
              ^
pipes.cpp:44:22: warning: unused variable 'idx' [-Wunused-variable]
     for(auto [to, idx]: adj[x]){
                      ^
pipes.cpp: In function 'int main()':
pipes.cpp:124:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < edges.size(); ++i)
                    ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2816 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 3456 KB Output is correct
2 Correct 10 ms 3456 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 3328 KB Output is correct
2 Correct 198 ms 3344 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 4224 KB Output is correct
2 Correct 449 ms 4232 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 659 ms 6220 KB Output is correct
2 Correct 599 ms 6900 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1291 ms 13036 KB Output is correct
2 Runtime error 1105 ms 31224 KB Memory limit exceeded

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2134 ms 14316 KB Output is correct
2 Runtime error 1993 ms 47336 KB Memory limit exceeded

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3236 ms 17004 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3981 ms 16924 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4923 ms 16236 KB Output is correct
2 Runtime error 4366 ms 65536 KB Memory limit exceeded