oj.uz

Submission #586919

# Submission time Handle Problem Language Result Execution time Memory
586919 2022-07-01T03:24:22 Z eecs Izlet (COI19_izlet) C++17
100 / 100
 747 ms 74648 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3010;
int n, a[maxn][maxn], fa[maxn];
vector<int> G[maxn];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> *new int >> n;
    iota(fa + 1, fa + n + 1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for (int x : {1, 2}) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][j] == x && find(i) ^ find(j)) {
                    fa[find(i)] = find(j);
                    G[i].push_back(j), G[j].push_back(i);
                }
            }
        }
    }
    iota(fa + 1, fa + n + 1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j : G[i]) {
            auto dfs = [&](auto self, int u, int p) -> void {
                int x = (u == j ? 0 : a[j][p]) + 1;
                if (a[i][u] == x && a[i][p] == x && a[j][u] == x) {
                    fa[find(i)] = find(u);
                }
                for (int v : G[u]) {
                    if (v ^ p) self(self, v, u);
                }
            };
            dfs(dfs, j, i);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << find(i) << " \n"[i == n];
    }
    for (int i = 1; i <= n; i++) {
        for (int j : G[i]) if (i < j) {
            cout << i << " " << j << "\n";
        }
    }
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 644 ms 53552 KB Output is correct
3 Correct 643 ms 53624 KB Output is correct
4 Correct 635 ms 53416 KB Output is correct
5 Correct 589 ms 53364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 36008 KB Output is correct
2 Correct 601 ms 53624 KB Output is correct
3 Correct 716 ms 73752 KB Output is correct
4 Correct 719 ms 74648 KB Output is correct
5 Correct 555 ms 53480 KB Output is correct
6 Correct 560 ms 60484 KB Output is correct
7 Correct 427 ms 49484 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 644 ms 53552 KB Output is correct
3 Correct 643 ms 53624 KB Output is correct
4 Correct 635 ms 53416 KB Output is correct
5 Correct 589 ms 53364 KB Output is correct
6 Correct 577 ms 36008 KB Output is correct
7 Correct 601 ms 53624 KB Output is correct
8 Correct 716 ms 73752 KB Output is correct
9 Correct 719 ms 74648 KB Output is correct
10 Correct 555 ms 53480 KB Output is correct
11 Correct 560 ms 60484 KB Output is correct
12 Correct 427 ms 49484 KB Output is correct
13 Correct 747 ms 54400 KB Output is correct
14 Correct 728 ms 61396 KB Output is correct
15 Correct 562 ms 53468 KB Output is correct
16 Correct 603 ms 58016 KB Output is correct
17 Correct 621 ms 60004 KB Output is correct
18 Correct 521 ms 53448 KB Output is correct
19 Correct 553 ms 53504 KB Output is correct
20 Correct 598 ms 53452 KB Output is correct
21 Correct 610 ms 54140 KB Output is correct
22 Correct 590 ms 53720 KB Output is correct
23 Correct 655 ms 54228 KB Output is correct
24 Correct 659 ms 60532 KB Output is correct
25 Correct 532 ms 53576 KB Output is correct