oj.uz

Submission #117685

# Submission time Handle Problem Language Result Execution time Memory
117685 2019-06-17T06:18:59 Z 김세빈(#2878) Izlet (COI19_izlet) C++14
100 / 100
 951 ms 37232 KB 
#include <bits/stdc++.h>

using namespace std;

int D[3030][3030], C[3030], P[3030];
vector <int> V[3030], T[3030];
int n, cnt;

int find(int p) { return p == P[p]? p : P[p] = find(P[p]); }
void unite(int p, int q) { P[find(p)] = find(q); }

void dfs2(int x, int y, int p, int r)
{
	if(D[x][p] == D[y][p]){
		C[x] = C[p];
		return;
	}

	for(int &t: V[p]){
		if(C[x]) return;
		if(t != r){
			dfs2(x, y, t, p);
		}
	}
}

void add(int p, int r)
{
	V[p].push_back(r);
	V[r].push_back(p);
	dfs2(p, r, r, p);
	if(!C[p]) C[p] = ++cnt;
}	

void dfs(int p, int r)
{
	for(int &t: T[p]){
		if(t != r){
			add(t, p);
			dfs(t, p);
		}
	}
}

int main()
{
	int i, j;

	scanf("%d%d", &n, &n);

	for(i=1; i<=n; i++){
		P[i] = i;
	}

	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			scanf("%d", D[i] + j);

			if(D[i][j] == 1 && find(i) != find(j)){
				unite(i, j);
				T[i].push_back(j);
				T[j].push_back(i);
			}
		}
	}

	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			if(D[i][j] == 2 && find(i) != find(j)){
				unite(i, j);
				T[i].push_back(j);
				T[j].push_back(i);
			}
		}
	}

	C[1] = ++cnt;

	dfs(1, 0);

	for(i=1; i<=n; i++){
		printf("%d ", C[i]);
	}

	printf("\n");

	for(i=1; i<=n; i++){
		for(int &t: T[i]){
			if(i < t) printf("%d %d\n", i, t);
		}
	}

	return 0;
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &n);
  ~~~~~^~~~~~~~~~~~~~~~
izlet.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", D[i] + j);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 724 ms 36788 KB Output is correct
3 Correct 951 ms 36800 KB Output is correct
4 Correct 731 ms 36880 KB Output is correct
5 Correct 734 ms 36900 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 36360 KB Output is correct
2 Correct 706 ms 36744 KB Output is correct
3 Correct 863 ms 37116 KB Output is correct
4 Correct 881 ms 37232 KB Output is correct
5 Correct 692 ms 36600 KB Output is correct
6 Correct 731 ms 36688 KB Output is correct
7 Correct 546 ms 30744 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 724 ms 36788 KB Output is correct
3 Correct 951 ms 36800 KB Output is correct
4 Correct 731 ms 36880 KB Output is correct
5 Correct 734 ms 36900 KB Output is correct
6 Correct 696 ms 36360 KB Output is correct
7 Correct 706 ms 36744 KB Output is correct
8 Correct 863 ms 37116 KB Output is correct
9 Correct 881 ms 37232 KB Output is correct
10 Correct 692 ms 36600 KB Output is correct
11 Correct 731 ms 36688 KB Output is correct
12 Correct 546 ms 30744 KB Output is correct
13 Correct 707 ms 36228 KB Output is correct
14 Correct 815 ms 36500 KB Output is correct
15 Correct 721 ms 36268 KB Output is correct
16 Correct 794 ms 36472 KB Output is correct
17 Correct 808 ms 36472 KB Output is correct
18 Correct 684 ms 36344 KB Output is correct
19 Correct 745 ms 36536 KB Output is correct
20 Correct 724 ms 36412 KB Output is correct
21 Correct 730 ms 36228 KB Output is correct
22 Correct 721 ms 36280 KB Output is correct
23 Correct 721 ms 36240 KB Output is correct
24 Correct 788 ms 36300 KB Output is correct
25 Correct 780 ms 36500 KB Output is correct