oj.uz

답안 #611778

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
611778 2022-07-29T07:25:21 Z 장태환(#8498) Izlet (COI19_izlet) C++17
100 / 100
 1588 ms 40164 KB 
#include <bits/stdc++.h>
using namespace std;
int N;
int arr[3010][3010];
int uf[3010];
vector<int>link[3010];
int f(int n)
{
	return uf[n] == n ? n : uf[n] = f(uf[n]);
}
void u(int n, int m)
{
	uf[f(n)] = uf[f(m)];
}
vector<int>r;
void dfs(int n, int p = -1)
{
	r.push_back(n);
	if (p!=-1)
	{
		int s = 0;
		int e = r.size() - 1;
		while (s != e)
		{
			int m = (s + e) / 2;
			if (arr[r[m]][p]!= arr[r[m]][n])
			{
				e = m;
			}
			else
			{
				s = m + 1;
			}
		}
		if (s)
		{
			u(r[s - 1], n);
		}
	}
	int i;
	for (i = 0; i < link[n].size(); i++)
	{
		if (link[n][i] == p)
			continue;
		dfs(link[n][i], n);
	}
	
	r.pop_back();
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t >> N;
	int i,j;
	for (i = 0; i < N; i++)
	{
		uf[i] = i;
		for (j = 0; j < N; j++)
		{
			cin >> arr[i][j];
		}
	}
	vector<pair<int, int>>ans;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (arr[i][j] == 1)
			{
				if (f(i) != f(j))
				{
					u(i, j);
					link[i].push_back(j);
					link[j].push_back(i);
					ans.push_back({ i + 1,j + 1 });
				}
			}
		}
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (arr[i][j] == 2)
			{
				if (f(i) != f(j))
				{
					u(i, j);
					link[i].push_back(j);
					link[j].push_back(i);
					ans.push_back({ i + 1,j + 1 });
				}
			}
		}
	}
	for (i = 0; i < N; i++)
		uf[i] = i;
	for (i = 0; i < N; i++)
	{
		dfs(i);
	}
	for (i = 0; i < N; i++)
		cout << f(i) + 1 << ' ';
	cout << '\n';
	for (i = 0; i < ans.size(); i++)
	{
		cout << ans[i].first << ' ' << ans[i].second << '\n';
	}
}

Compilation message

izlet.cpp: In function 'void dfs(int, int)':
izlet.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (i = 0; i < link[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:107:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (i = 0; i < ans.size(); i++)
      |              ~~^~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 685 ms 36468 KB Output is correct
3 Correct 693 ms 36476 KB Output is correct
4 Correct 770 ms 36416 KB Output is correct
5 Correct 688 ms 36364 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1097 ms 36448 KB Output is correct
2 Correct 755 ms 40072 KB Output is correct
3 Correct 1588 ms 38928 KB Output is correct
4 Correct 1037 ms 38944 KB Output is correct
5 Correct 760 ms 40164 KB Output is correct
6 Correct 922 ms 37936 KB Output is correct
7 Correct 743 ms 31808 KB Output is correct

Subtask #3
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 685 ms 36468 KB Output is correct
3 Correct 693 ms 36476 KB Output is correct
4 Correct 770 ms 36416 KB Output is correct
5 Correct 688 ms 36364 KB Output is correct
6 Correct 1097 ms 36448 KB Output is correct
7 Correct 755 ms 40072 KB Output is correct
8 Correct 1588 ms 38928 KB Output is correct
9 Correct 1037 ms 38944 KB Output is correct
10 Correct 760 ms 40164 KB Output is correct
11 Correct 922 ms 37936 KB Output is correct
12 Correct 743 ms 31808 KB Output is correct
13 Correct 1306 ms 37252 KB Output is correct
14 Correct 909 ms 37692 KB Output is correct
15 Correct 796 ms 39776 KB Output is correct
16 Correct 790 ms 37520 KB Output is correct
17 Correct 883 ms 37620 KB Output is correct
18 Correct 763 ms 39768 KB Output is correct
19 Correct 638 ms 39908 KB Output is correct
20 Correct 874 ms 39968 KB Output is correct
21 Correct 741 ms 37236 KB Output is correct
22 Correct 763 ms 37212 KB Output is correct
23 Correct 878 ms 37148 KB Output is correct
24 Correct 982 ms 37632 KB Output is correct
25 Correct 845 ms 37280 KB Output is correct