oj.uz

Submission #117650

# Submission time Handle Problem Language Result Execution time Memory
117650 2019-06-17T04:23:42 Z 조승현(#2884) Izlet (COI19_izlet) C++14
100 / 100
 1562 ms 74972 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, w[3010][3010], par[3010], D[3010], vis[3010], Col[3010], cnt, dis[3010][3010];
vector<int>E[3010];
void Make(int a, int b) {
	par[b] = a;
	E[a].push_back(b);
	E[b].push_back(a);
	int i;
	for (i = 1; i <= n; i++) {
		if (vis[i])dis[i][b] = dis[b][i] = dis[a][i] + 1;
	}
}
int main() {
	int i, sub, j;
	scanf("%d%d", &sub, &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			scanf("%d", &w[i][j]);
		}
	}
	vis[1] = 1;
	Col[1] = 1;
	cnt = 1;
	for (i = 1; i <= n; i++)D[i] = w[1][i];
	for (int T = 2; T <= n; T++) {
		int Mn = 1e9, pv = -1;
		for (i = 1; i <= n; i++) {
			if (!vis[i] && Mn > D[i]) {
				Mn = D[i], pv = i;
			}
		}
		for (i = 1; i <= n; i++)D[i] = min(D[i], w[pv][i]);
		int pp = -1;
		for (i = 1; i <= n; i++) {
			if (vis[i] && w[i][pv] == Mn)pp = i;
		}
		Make(pp, pv);
		vis[pv] = 1;
		if (Mn == 1) {
			Col[pv] = Col[pp];
			continue;
		}
		int Mn2 = 1e9, pv2 = -1;
		for (i = 1; i <= n; i++) {
			if (vis[i] && w[i][pp] == w[i][pv] && Mn2 > dis[pv][i]) {
				Mn2 = dis[pv][i];
				pv2 = i;
			}
		}
		if (pv2 == -1)Col[pv] = ++cnt;
		else Col[pv] = Col[pv2];
	}
	for (i = 1; i <= n; i++)printf("%d ", Col[i]);
	puts("");
	for (i = 2; i <= n; i++)printf("%d %d\n", par[i], i);
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &sub, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:21:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &w[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 988 ms 72484 KB Output is correct
3 Correct 989 ms 72496 KB Output is correct
4 Correct 1358 ms 74912 KB Output is correct
5 Correct 1077 ms 74616 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 71480 KB Output is correct
2 Correct 933 ms 72540 KB Output is correct
3 Correct 1089 ms 74972 KB Output is correct
4 Correct 1122 ms 74872 KB Output is correct
5 Correct 936 ms 72460 KB Output is correct
6 Correct 969 ms 72776 KB Output is correct
7 Correct 699 ms 61480 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 988 ms 72484 KB Output is correct
3 Correct 989 ms 72496 KB Output is correct
4 Correct 1358 ms 74912 KB Output is correct
5 Correct 1077 ms 74616 KB Output is correct
6 Correct 1116 ms 71480 KB Output is correct
7 Correct 933 ms 72540 KB Output is correct
8 Correct 1089 ms 74972 KB Output is correct
9 Correct 1122 ms 74872 KB Output is correct
10 Correct 936 ms 72460 KB Output is correct
11 Correct 969 ms 72776 KB Output is correct
12 Correct 699 ms 61480 KB Output is correct
13 Correct 1444 ms 72436 KB Output is correct
14 Correct 1562 ms 72952 KB Output is correct
15 Correct 1259 ms 72696 KB Output is correct
16 Correct 1355 ms 72760 KB Output is correct
17 Correct 1409 ms 72824 KB Output is correct
18 Correct 1027 ms 72508 KB Output is correct
19 Correct 1125 ms 72620 KB Output is correct
20 Correct 1279 ms 72440 KB Output is correct
21 Correct 1238 ms 72400 KB Output is correct
22 Correct 1310 ms 72440 KB Output is correct
23 Correct 1318 ms 72452 KB Output is correct
24 Correct 1496 ms 72984 KB Output is correct
25 Correct 1363 ms 72448 KB Output is correct