oj.uz

Submission #96797

# Submission time Handle Problem Language Result Execution time Memory
96797 2019-02-12T03:41:38 Z Retro3014 Pipes (CEOI15_pipes) C++17
70 / 100
 5000 ms 16616 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
#define MAX_N 100000
typedef long long ll;
typedef pair<int, int> pii;

int N, M;
vector<pii > gp[MAX_N+1];
int g[MAX_N+1];
int num[MAX_N+1];
int p[MAX_N+1][20];
int up[MAX_N+1];
int lv[MAX_N+1];
bool vst[MAX_N+1];

void init_g(){
	for(int i=1; i<=N; i++)	g[i] = i;
	for(int i=1; i<=N; i++)	num[i] = 1;
}

int find_g(int x){
	if(x==g[x])	return x;
	return g[x] = find_g(g[x]);
}

void union_g(int x, int y){
	x = find_g(x); y = find_g(y);
	g[x] = y;
	num[y] += num[x];
}

vector<pii> edge;
vector<bool> chk;

int lca(int x, int y){
	for(int i=19; i>=0; i--){
		//cout<<i<<' '<<x<<' '<<y<<endl;
		if(lv[p[x][i]]>=lv[y]){
			x = p[x][i];
		}
		if(lv[p[y][i]]>=lv[x]){
			y = p[y][i];
		}
	}
	for(int i=19; i>=0; i--){
		if(p[x][i]!=p[y][i]){
			x = p[x][i]; y = p[y][i];
		}
	}
	if(x!=y)	x = p[x][0];
	return x;
}

void dfs(int x){
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i].first==p[x][0])	continue;
		dfs(gp[x][i].first);
		if(up[gp[x][i].first]<=lv[x])	chk[gp[x][i].second] = false;
		up[x] = min(up[x], up[gp[x][i].first]);
	}
}

void init_graph(int x){
	up[x] = lv[x];
	for(int i=1; i<20; i++)	p[x][i] = p[p[x][i-1]][i-1];
	for(int i=0; i<gp[x].size(); i++){
		if(gp[x][i].first==p[x][0])	continue;
		lv[gp[x][i].first] = lv[x]+1;
		p[gp[x][i].first][0] = x;
		init_graph(gp[x][i].first);
	}
}



int main(){
	scanf("%d%d", &N, &M);
	int a, b, k, tmp;
	init_g();
	for(int i=1; i<=N; i++){
		lv[i] = up[i] = 1;
	}
	while(M--){
		scanf("%d%d", &a, &b);
		if(find_g(a)==find_g(b)){
			//cout<<'*'<<a<<' '<<b<<endl;
			k = lca(a, b);
			//cout<<k<<endl;
			up[a] = min(up[a], lv[k]);
			up[b] = min(up[b], lv[k]);
		}else{
			if(num[find_g(a)]>=num[find_g(b)]){
				tmp = a; a = b; b = tmp;
			}
			dfs(find_g(a));
			for(int i=1; i<20; i++){
				p[a][i] = 0;
			}p[a][0] = b;
			lv[a] = lv[b]+1;
			//printf("%d %d\n", a, b);
			gp[a].push_back({b, (int)edge.size()});
			gp[b].push_back({a, (int)edge.size()});
			init_graph(a);
			edge.push_back({a, b});
			chk.push_back(true);
			union_g(a, b);
		}
	}
	for(int i=1; i<=N; i++){
		if(!vst[find_g(i)]){
			vst[find_g(i)] = true;
			dfs(find_g(i));
		}
	}
	for(int i=0; i<edge.size(); i++){
		if(chk[i]){
			printf("%d %d\n", edge[i].first, edge[i].second);
		}
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(int)':
pipes.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
pipes.cpp: In function 'void init_graph(int)':
pipes.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:119:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<edge.size(); i++){
               ~^~~~~~~~~~~~
pipes.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 3200 KB Output is correct
2 Correct 243 ms 3204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 4084 KB Output is correct
2 Correct 585 ms 4068 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 5996 KB Output is correct
2 Correct 664 ms 6752 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1448 ms 12656 KB Output is correct
2 Correct 1309 ms 12676 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2216 ms 13828 KB Output is correct
2 Correct 2099 ms 13716 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3329 ms 16384 KB Output is correct
2 Runtime error 3406 ms 16616 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4270 ms 16364 KB Output is correct
2 Runtime error 4235 ms 16560 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 15692 KB Time limit exceeded
2 Halted 0 ms 0 KB -