Submission #1116024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116024		dosts	Pipes (CEOI15_pipes)	C++17	0 / 100	4 ms	1872 KiB

pipes

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
int MOD = 998244353,inf = 2e9;
const int N = 1e4+50,Q = 2e5+50;
int dad[N],cur[N];
int d1[N],d2[N];
vector<pair<int,pii>> edges[N],newedges;
vi traverse,traverse2;
struct DSU {
    void bfs(int node) {
        d1[node] = 0;
        queue<int> q;
        q.push(node);
        while (!q.empty()) {
            int f = q.front();
            traverse2.push_back(f);
            q.pop();
            for (auto it : edges[f]) {
                if (d1[cur[it.ff]] == -1) {
                    d1[cur[it.ff]] = d1[f]+1;
                    q.push(cur[it.ff]);
                }
                if (it.ff != cur[it.ff]) edges[it.ff].clear();
            }
        }
    }

    void bfs2(int node) {
        d2[node] = 0;
        queue<int> q;
        q.push(node);
        while (!q.empty()) {
            int f = q.front();
            //cout << "REACH" sp f sp d2[f] << '\n';
            traverse.push_back(f);
            q.pop();
            for (auto it : edges[f]) {
                if (d2[cur[it.ff]] == -1) {
                    d2[cur[it.ff]] = d2[f]+1;
                    q.push(cur[it.ff]);
                }
                if (it.ff != cur[it.ff]) edges[it.ff].clear();
            }
        }
    }

    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }

    void unite(int a,int b,int aa,int bb) {
        int x = find(a),y = find(b);
        if (x == y) {
            bfs(a);
            bfs2(b);
            int dist = d1[b];
            int newname = inf;
            for (auto it : traverse) if (d1[it]+d2[it] == dist) newname = min(newname,cur[it]);
            for (auto it : traverse) {
                if (d1[it]+d2[it] != dist) continue;
                cur[it] = newname;
                for (auto itt : edges[it]) {
                    if (d1[cur[itt.ff]]+d2[cur[itt.ff]] != dist) newedges.push_back({cur[itt.ff],itt.ss});
                }
                edges[it].clear();
            }
            edges[newname].swap(newedges);
            sort(all(traverse));
            sort(all(traverse2));
            assert(traverse == traverse2);
            traverse.clear();
            traverse2.clear();
            newedges.clear();
        }
        else {
            dad[x] = y;
            edges[a].push_back({b,{aa,bb}});
            edges[b].push_back({a,{bb,aa}});
        }
    }
};
void solve() {
    memset(d1,-1,sizeof d1);
    memset(d2,-1,sizeof d2);
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) dad[i] = i,cur[i] = i;
    DSU dsu;
    for (int i=0;i<m;i++) {
        int a,b;
        cin >> a >> b;
        dsu.unite(cur[a],cur[b],a,b);
    }
    for (int i=1;i<=n;i++) {
        for (auto it : edges[i]) {
            if (cur[it.ss.ff] != cur[it.ss.ss] && it.ss.ff < it.ss.ss) {
                cout << it.ss.ff sp it.ss.ss << '\n';
            }
        }
    }
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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