oj.uz

답안 #82356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82356 2018-10-30T08:59:21 Z aminra Pipes (CEOI15_pipes) C++14
40 / 100
 369 ms 10360 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int MAXN = (int)10004;
const int MAXS = (int)1200003;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int par[MAXN], u[MAXS], v[MAXS], n, m, h[MAXN];
bool val[MAXN];
bool used[MAXS];
vector<int> G[MAXN];
int parent(int u)
{
	return par[u] < 0 ? u : par[u] = parent(par[u]);
}
void merge(int u, int v)
{
	if(par[u] < par[v])
		swap(u, v); //alan size u < size v.
	par[v] += par[u];
	par[u] = v;
}
void dfs(int u, int pa)
{
	par[u] = pa;
	for (auto v : G[u])
		if(v != pa)
		{
			h[v] = h[u] + 1;
			dfs(v, u);
		}
}
void add(int u, int v)
{
	while(u != v)
	{
		if(h[u] > h[v])
		{
			val[u] = 1;
			u = par[u];
		}
		else
		{
			val[v] = 1;
			v = par[v];
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	memset(par, -1, sizeof par);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> u[i] >> v[i];
		if(parent(u[i]) != parent(v[i]))
		{
			merge(parent(u[i]), parent(v[i]));
			used[i] = 1;
			G[u[i]].push_back(v[i]);
			G[v[i]].push_back(u[i]);
		}
	}
	for (int i = 1; i <= n; i++)
		if(par[i] < 0)
			dfs(i, -1);
	for (int i = 0; i < m; i++)
		if(!used[i])
			add(u[i], v[i]);
	
	for (int i = 1; i <= n; i++)
		if(par[i] != -1 && val[i] == 0)
			cout << i << " " << par[i] << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -