Submission #731647

#	Time	Username	Problem	Language	Result	Execution time	Memory
731647		esomer	Pipes (CEOI15_pipes)	C++17	40 / 100	1865 ms	65536 KiB

pipes

#include<bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"

typedef long long int ll;
 
const int MOD = 1e9 + 7;

struct DSU{
	vector<int> v;
	void init(int n){
		v.assign(n, -1);
	}
	int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
	bool unite(int x, int y){
		x = get(x); y = get(y);
		if(x == y) return 0;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
		return 1;
	}
};

int cnt = 1;

void DFS(int x, vector<vector<int>>& adj, vector<pair<int, int>>& id, int p){
	id[x].first = cnt; cnt++;
	for(int node : adj[x]){
		if(id[node].first > 0) continue;
		DFS(node, adj, id, x);
	}
	id[x].second = cnt; cnt++;
}

void get_ans(int x, vector<vector<int>>& adj, vector<bool>& vis, vector<pair<int, int>>& id, vector<pair<int, int>>& mn, int p){
	vis[x] = 1;
	for(int node : adj[x]){
		if(node == p) continue;
		get_ans(node, adj, vis, id, mn, x);
		mn[x].first = min(mn[x].first, mn[node].first);
		mn[x].second = max(mn[x].second, mn[node].second);
		if(!(mn[node].first < id[node].first || mn[node].second > id[node].second)){
			cout << node + 1 << " " << x + 1 << endl;
		}
	}
}

void solve(){
	int n, m; cin >> n >> m;
	vector<vector<int>> adj(n);
	DSU UF; UF.init(n);
	vector<int> done;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v; u--; v--;
		if(UF.unite(v, u)) {adj[u].push_back(v); adj[v].push_back(u); done.push_back(i);}
	}
	vector<pair<int, int>> id(n, {0, 0});
	for(int i = 0; i < n; i++){
		if(id[i].first == 0){
			DFS(i, adj, id, -1);
		}
	}
	rewind(stdin);
	cin >> n >> m;
	vector<pair<int, int>> mn(n);
	for(int i = 0; i < n; i++) mn[i] = {id[i].first, id[i].second};
	int ind = 0;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v; u--; v--;
		if(ind < (int)done.size() && done[ind] == i){
			ind++; continue;
		}
		mn[u].first = min(mn[u].first, id[v].first);
		mn[u].second = max(mn[u].second, id[v].second);
		mn[v].first = min(mn[v].first, id[u].first);
		mn[v].second = max(mn[v].second, id[u].second);
	}
	vector<bool> vis(n, 0);
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			get_ans(i, adj, vis, id, mn, -1);
		}
	}
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //~ int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 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