oj.uz

답안 #910836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
910836 2024-01-18T08:24:43 Z asdasdqwer Pipes (CEOI15_pipes) C++14
70 / 100
 807 ms 18596 KB 
    #include <bits/stdc++.h>
    using namespace std;
     
    struct DSU {
        vector<int> p,r;
        DSU(int n) : p(n),r(n,1) {
            for (int i=0;i<n;i++)p[i]=i;
        }
     
        int get(int i) {
            if (p[i]!=i && p[i]!=p[p[i]]) p[i]=get(p[i]);
            return p[i];
        }
     
        bool unite(int a,int b) {
            a=get(a),b=get(b);
            if (a==b)return false;
            if (r[a]<r[b])swap(a,b);
            p[b]=a;
            r[a]+=r[b];
            return true;
        }
    };
     
     
    vector<int> st(1e5+1, 0);
     
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
     
        int n,m;cin>>n>>m;
        DSU d1(n), d2(n);
        vector<vector<int>> g(n);
     
        for (int i=0;i<m;i++) {
            int a,b;cin>>a>>b;a--;b--;
            if (d1.unite(a,b)) {
                g[a].push_back(b);
                g[b].push_back(a);
            }
     
            else {
                d2.unite(a,b);
            }
        }
     
        d1.r.clear();
        d2.r.clear();
     
        vector<vector<int>> lft(n, vector<int>(18, -1));
        bitset<100001> vis;
        vector<int> d(n,0);
     
        for (int i=0;i<n;i++) {
            if (vis[i]) continue;
            int pt=0;
            st[pt]=i;
            vis[i]=true;
            while (pt != -1) {
                int r=st[pt--];
                for (int x:g[r]) {
                    if (!vis[x]) {
                        vis[x]=true;
                        lft[x][0]=r;
                        d[x]=d[r]+1;
                        st[++pt]=x;
                    }
                }
            }
        }
     
        for (int j=1;j<18;j++) {
            for (int i=0;i<n;i++) {
                lft[i][j]=lft[i][j-1];
                if (lft[i][j] != -1) {
                    lft[i][j]=lft[lft[i][j]][j-1];
                }
            }
        }
     
        vector<int> dp(n, 0);
     
        for (int i=0;i<n;i++) {
            if (d2.p[i] == i) continue;
            int a=i, b=d2.get(i);
            dp[a]++;
            dp[b]++;
     
            if (d[a]<d[b])swap(a,b);
            int steps=d[a]-d[b];
            int cnt=0;
            while (steps) {
                if ((steps&1)==1) {
                    a=lft[a][cnt];
                }
                steps>>=1;cnt++;
            }
            
            if (a==b) {
                dp[a]-=2;
                continue;
            }
     
            for (int i=17;i>-1;--i) {
                if (lft[a][i] != lft[b][i]) {
                    a=lft[a][i];
                    b=lft[b][i];
                }
            }
     
            dp[lft[a][0]] -= 2;
        }
     
        d.clear();
        for (int i=0;i<n;i++) {
            lft[i]={lft[i][0]};
        }
     
        for (int i=0;i<n;i++) vis[i]=0;
     
        for (int i=0;i<n;i++) {
            st[i]=-1;
        }
     
        for (int i=0;i<n;i++) {
            if (vis[i])continue;
            int pt=0;
            vis[i]=true;
            st[0]=i;
            while (pt != -1) {
                int r=st[pt];
                if (g[r].size()==0) {
                    if (lft[r][0] != -1) {
                        dp[lft[r][0]] += dp[r];
                    }
                    pt--;
                    continue;
                }
     
                for (int x:g[r]) {
                    if (!vis[x]) {
                        st[++pt]=x;
                        vis[x]=true;
                    }
                }
     
                g[r].clear();
            }
        }
     
        st.clear();
     
        for (int i=0;i<n;i++) {
            if (dp[i]==0 && lft[i][0] != -1) {
                cout<<i+1<<" "<<lft[i][0]+1<<"\n";
            }
        }
     
        dp.clear();
        lft.clear();
     
        return 0;
    }

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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