Submission #218910

#	Time	Username	Problem	Language	Result	Execution time	Memory
218910		dolphingarlic	Izlet (COI19_izlet)	C++14	100 / 100	778 ms	109680 KiB

izlet

#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 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57