oj.uz

답안 #117678

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117678 2019-06-17T06:00:20 Z 김세빈(#2878) Izlet (COI19_izlet) C++14
0 / 100
 723 ms 36344 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 p, int r, int d)
{
	if(D[x][p] != d){
		C[x] = C[p];
		return;
	}

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

void add(int p, int r)
{
	V[p].push_back(r);
	V[r].push_back(p);
	dfs2(p, p, 0, 1);
	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
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 723 ms 36344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -