Submission #234281

#	Time	Username	Problem	Language	Result	Execution time	Memory
234281		VEGAnn	Izlet (COI19_izlet)	C++14	100 / 100	792 ms	40856 KiB

izlet

#include <bits/stdc++.h>
#define PB push_back
#define a2 array<int,2>
using namespace std;
const int N = 3010;
const int M = 1010;
const int oo = 2e9;
vector<int> g[N];
vector<a2> vc;
int ans[N], a[N][N], n, kol = 0, gl, cnt, col[N], pr[N];
bool is_cen[N], mrk[N];

int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x]));}

void add_edge(int x, int y){
    vc.PB({x, y});
    g[x].PB(y);
    g[y].PB(x);
}

void check(int v, int pr, int len){
    if (col[ans[v]] == 0)
        cnt++;
    col[ans[v]]++;

    if (cnt == a[gl][v]){
        ans[gl] = ans[v];

        col[ans[v]]--;
        if (col[ans[v]] == 0)
            cnt--;
        return;
    }

    for (int u : g[v]){
        if (u == pr) continue;
        if (ans[u] == 0) continue;

        check(u, v, len + 1);
    }

    col[ans[v]]--;
    if (col[ans[v]] == 0)
        cnt--;
}

void dfs(int v, int p){
    gl = v;
    for (int u : g[v])
        if (ans[u] > 0)
            check(u, v, 1);

    if (ans[gl] == 0)
        ans[gl] = ++kol;

    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> n;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        cin >> a[i][j];

    vc.clear();

    for (int i = 0; i < n; i++){
        pr[i] = i;

        if (mrk[i]) continue;

        is_cen[i] = 1;

        int cen = i;

        for (int j = i + 1; j < n; j++){
            if (ans[j] > 0) continue;

            if (a[i][j] == 1) {
                add_edge(cen, j);
                mrk[j] = 1;
            }
        }
    }

    for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++){
        if (!is_cen[i] || !is_cen[j]) continue;
        if (a[i][j] != 2) continue;
        if (get(i) == get(j)) continue;

        add_edge(i, j);
        pr[get(i)] = get(j);

        for (int z = 0; z < n; z++){
            if (z == i || z == j || !is_cen[z]) continue;

            if (a[z][i] == 2 && a[z][j] == 2) {
                add_edge(i, z);
                pr[get(i)] = get(z);
            }
        }
    }

    dfs(0, -1);

    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << '\n';

    for (a2 cr : vc)
        cout << cr[0] + 1 << " " << cr[1] + 1 << '\n';

    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57