oj.uz

Submission #731657

# Submission time Handle Problem Language Result Execution time Memory
731657 2023-04-27T18:01:12 Z esomer Pipes (CEOI15_pipes) C++17
100 / 100
 2250 ms 8424 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
//~ #define endl "\n"

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

int cnt = 1;
pair<int, int> id[N], mn[N];
vector<int> adj[N];
int v[N];
bool vis[N];

struct DSU{
	void init(int n){
		for(int i = 0; i < n; i++) v[i] = -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;
	}
};


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

void get_ans(int x, int p){
	vis[x] = 1;
	for(int node : adj[x]){
		if(node == p) continue;
		get_ans(node, 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)){
			printf("%d %d\n", node + 1, x + 1);
		}
	}
}

void solve(){
	int n, m;
	scanf("%d%d", &n, &m);
	DSU UF; UF.init(n);
	vector<int> done;
	for(int i = 0; i < m; i++){
		int u, v; 
		scanf("%d%d", &u, &v);
		u--; v--;
		if(UF.unite(v, u)) {adj[u].push_back(v); adj[v].push_back(u); done.push_back(i);}
	}
	for(int i = 0; i < n; i++) id[i] = {0, 0};
	for(int i = 0; i < n; i++){
		if(id[i].first == 0){
			DFS(i);
		}
	}
	rewind(stdin);
	scanf("%d%d", &n, &m);
	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; 
		scanf("%d%d", &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);
	}
	for(int i = 0; i < n; i++) vis[i] = 0;
	for(int i = 0; i < n; i++){
		if(!vis[i]){
			get_ans(i, -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();
    }
}

Compilation message

pipes.cpp: In function 'void solve()':
pipes.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2900 KB Output is correct
2 Correct 6 ms 2900 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 2852 KB Output is correct
2 Correct 199 ms 2844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 3164 KB Output is correct
2 Correct 389 ms 3172 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 3964 KB Output is correct
2 Correct 510 ms 4288 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 6516 KB Output is correct
2 Correct 595 ms 6504 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 7112 KB Output is correct
2 Correct 1098 ms 7080 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 8116 KB Output is correct
2 Correct 1334 ms 8248 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1872 ms 8148 KB Output is correct
2 Correct 1632 ms 8256 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2151 ms 7912 KB Output is correct
2 Correct 2250 ms 8424 KB Output is correct