제출 #1197122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197122		HasanV11010238	Pipes (CEOI15_pipes)	C++20	90 / 100	1434 ms	13700 KiB

pipes

#include <bits/stdc++.h>
#define ll long long
#define MAX 100000
#define INF 1000000000000000
#define mod 998244353
using namespace std;
int up[MAX + 1][17], de[MAX + 1], ans[MAX + 1];
vector<vector<int>> v;
void dfs(int x, int p){
    up[x][0] = p, de[x] = de[p] + 1;
    for (int i = 1; i < 17; i++){
        up[x][i] = up[up[x][i - 1]][i - 1];
    }
    for (auto el : v[x]){
        if (el != p) dfs(el, x);
    }
}
int p[MAX + 1];
int find(int x){
    if (p[x] < 0) return x;
    return p[x] = find(p[x]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if (a == b) return;
    if (p[a] > p[b]) swap(a, b);
    p[a] += p[b];
    p[b] = a;
}
int gs(int x){
    return -p[find(x)];
}
int dist(int x, int k){
    for (int i = 0; i < 17; i++){
        int val = k & (1<<i);
        if (val != 0) x = up[x][i];
    }
    return x;
}
int lca(int a, int b){
    if (de[a] > de[b]) swap(a, b);
    b = dist(b, de[b] - de[a]);
    if (a == b) return a;
    for (int i = 16; i >= 0; i--){
        if (up[a][i] != up[b][i]){
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}
void dfs2(int x, int p){
    for (auto el : v[x]){
        if (el != p){
            dfs2(el, x);
            ans[x] += ans[el];
        }
    }
    if (ans[x] == 0 && p != 0) cout<<x<<" "<<p<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, a, b;
    cin>>n>>m;
    for (int i = 1; i <= n; i++) p[i] = -1, de[i] = 1;
    v.assign(n + 1, vector<int>());
    for (int i = 0; i < m; i++){
        cin>>a>>b;
        int ra = find(a), rb = find(b);
        if (ra != rb){
            v[a].push_back(b);
            v[b].push_back(a);
            if (p[ra] > p[rb]){
                dfs(a, b);
            }
            else{
                dfs(b, a);
            }
            merge(ra, rb);
        }
        else{
            int lc = lca(a, b);
            ans[a]++, ans[b]++, ans[lc] -= 2;
        }
    }
    for (int i = 1; i <= n; i++) if (de[i] == 1) dfs2(i, 0);
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10