oj.uz

Submission #117691

# Submission time Handle Problem Language Result Execution time Memory
117691 2019-06-17T06:34:34 Z 윤지학(#2883) Izlet (COI19_izlet) C++14
100 / 100
 954 ms 36500 KB 
#include <cstdio>
#include <vector>

using namespace std;

short a[3003][3003], b[3003][3003], w, z;
vector<int> g[3003];
int p[3003], q[3003];

int f(int *x, int y) {
	int t, tt;
	for (t = y; x[t] != t; t = x[t]);
	while (x[y] != y) {
		tt = x[y];
		x[y] = t;
		y = tt;
	}
	return t;
}

void dfs(int x, int y) {
	b[w][x] = z;
	for (auto t : g[x]) if (t != y) dfs(t, x);
}

int main() {
	int i, j, k, n;
	scanf("%*s%d", &n);
	for (i = 0; i < n; i++) p[i] = q[i] = i;
	for (i = 0; i < n; i++) for (j = 0; j < n; j++) {
		scanf("%hd", &a[i][j]);
		if (a[i][j] == 1 && f(p, i) != f(p, j)) {
			p[p[i]] = p[j];
			g[i].push_back(j);
			g[j].push_back(i);
			q[f(q, i)] = f(q, j);
		}
	}
	for (i = 0; i < n; i++) for (j = 0; j < i; j++) if (a[i][j] == 2 && f(p, i) != f(p, j)) {
		p[p[i]] = p[j];
		g[i].push_back(j);
		g[j].push_back(i);
	}
	for (i = 0; i < n; i++) for (auto t : g[i]) {
		w = i;
		z = t;
		dfs(t, i);
	}
	for (i = 0; i < n; i++) for (j = 0; j < i; j++) if (a[i][j] == a[b[i][j]][j] && a[i][j] == a[i][b[j][i]] && a[i][j] == a[b[i][j]][b[j][i]] + 1) {
		q[f(q, i)] = f(q, j);
	}
	for (i = 0; i < n; i++) printf("%hd ", f(q, i) + 1); puts("");
	for (i = 0; i < n; i++) for (auto t : g[i]) if (t < i) printf("%d %d\n", t + 1, i + 1);
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:52:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (i = 0; i < n; i++) printf("%hd ", f(q, i) + 1); puts("");
  ^~~
izlet.cpp:52:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (i = 0; i < n; i++) printf("%hd ", f(q, i) + 1); puts("");
                                                       ^~~~
izlet.cpp:27:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, n;
            ^
izlet.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%*s%d", &n);
  ~~~~~^~~~~~~~~~~~~
izlet.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%hd", &a[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 809 ms 36384 KB Output is correct
3 Correct 819 ms 36244 KB Output is correct
4 Correct 810 ms 36392 KB Output is correct
5 Correct 800 ms 36396 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 36144 KB Output is correct
2 Correct 854 ms 36128 KB Output is correct
3 Correct 954 ms 36500 KB Output is correct
4 Correct 943 ms 36496 KB Output is correct
5 Correct 782 ms 36200 KB Output is correct
6 Correct 813 ms 36304 KB Output is correct
7 Correct 601 ms 30456 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 809 ms 36384 KB Output is correct
3 Correct 819 ms 36244 KB Output is correct
4 Correct 810 ms 36392 KB Output is correct
5 Correct 800 ms 36396 KB Output is correct
6 Correct 826 ms 36144 KB Output is correct
7 Correct 854 ms 36128 KB Output is correct
8 Correct 954 ms 36500 KB Output is correct
9 Correct 943 ms 36496 KB Output is correct
10 Correct 782 ms 36200 KB Output is correct
11 Correct 813 ms 36304 KB Output is correct
12 Correct 601 ms 30456 KB Output is correct
13 Correct 911 ms 36088 KB Output is correct
14 Correct 912 ms 35908 KB Output is correct
15 Correct 800 ms 36116 KB Output is correct
16 Correct 855 ms 35912 KB Output is correct
17 Correct 877 ms 36088 KB Output is correct
18 Correct 779 ms 36128 KB Output is correct
19 Correct 820 ms 36036 KB Output is correct
20 Correct 826 ms 36060 KB Output is correct
21 Correct 826 ms 35788 KB Output is correct
22 Correct 817 ms 35908 KB Output is correct
23 Correct 873 ms 35960 KB Output is correct
24 Correct 866 ms 36028 KB Output is correct
25 Correct 800 ms 36088 KB Output is correct