oj.uz

Submission #218910

# Submission time Handle Problem Language Result Execution time Memory
218910 2020-04-03T05:51:47 Z dolphingarlic Izlet (COI19_izlet) C++14
100 / 100
 778 ms 109680 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int k, n, a[3001][3001], apsp[3001][3001];
int colour[3001], cnt = 1;
bool visited[3001];
vector<int> in_tree;
vector<pair<int, int>> edges;

void dfs(int node = 1) {
    visited[node] = true;
    in_tree.push_back(node);

    FOR(i, 1, n + 1) if (!visited[i] && a[node][i] == 1) {
        visited[i] = true;
        colour[i] = colour[node];
        for (int j : in_tree) apsp[i][j] = apsp[j][i] = apsp[node][j] + 1;
        edges.push_back({node, i});
    }

    FOR(i, 1, n + 1) if (!visited[i] && a[node][i] == 2) {
        int mn_same = 0;
        for (int j : in_tree) {
            apsp[i][j] = apsp[j][i] = apsp[node][j] + 1;
            if (a[i][j] == a[node][j] && (!mn_same || apsp[i][j] < apsp[i][mn_same])) mn_same = j;
        }
        if (mn_same) colour[i] = colour[mn_same];
        else colour[i] = ++cnt;
        edges.push_back({node, i});
        dfs(i);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> k >> n;
    FOR(i, 1, n + 1) FOR(j, 1, n + 1) cin >> a[i][j];
    colour[1] = 1;
    dfs();

    FOR(i, 1, n + 1) cout << colour[i] << ' ';
    cout << '\n';
    for (pair<int, int> i : edges) cout << i.first << ' ' << i.second << '\n';
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 583 ms 88696 KB Output is correct
3 Correct 617 ms 88952 KB Output is correct
4 Correct 563 ms 76152 KB Output is correct
5 Correct 568 ms 82296 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 87068 KB Output is correct
2 Correct 546 ms 84984 KB Output is correct
3 Correct 778 ms 109048 KB Output is correct
4 Correct 745 ms 109680 KB Output is correct
5 Correct 498 ms 82036 KB Output is correct
6 Correct 569 ms 92532 KB Output is correct
7 Correct 431 ms 75512 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 583 ms 88696 KB Output is correct
3 Correct 617 ms 88952 KB Output is correct
4 Correct 563 ms 76152 KB Output is correct
5 Correct 568 ms 82296 KB Output is correct
6 Correct 570 ms 87068 KB Output is correct
7 Correct 546 ms 84984 KB Output is correct
8 Correct 778 ms 109048 KB Output is correct
9 Correct 745 ms 109680 KB Output is correct
10 Correct 498 ms 82036 KB Output is correct
11 Correct 569 ms 92532 KB Output is correct
12 Correct 431 ms 75512 KB Output is correct
13 Correct 627 ms 89484 KB Output is correct
14 Correct 726 ms 96560 KB Output is correct
15 Correct 558 ms 87412 KB Output is correct
16 Correct 600 ms 92280 KB Output is correct
17 Correct 613 ms 88440 KB Output is correct
18 Correct 655 ms 88692 KB Output is correct
19 Correct 536 ms 82680 KB Output is correct
20 Correct 552 ms 87412 KB Output is correct
21 Correct 560 ms 84468 KB Output is correct
22 Correct 576 ms 88556 KB Output is correct
23 Correct 590 ms 88948 KB Output is correct
24 Correct 636 ms 95696 KB Output is correct
25 Correct 514 ms 88180 KB Output is correct