Submission #117391

#	Time	Username	Problem	Language	Result	Execution time	Memory
117391		keko37	Izlet (COI19_izlet)	C++14	100 / 100	744 ms	53712 KiB

izlet

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 3005;

int tip, n, cnt;
int a[MAXN][MAXN];
int bio[MAXN], par[MAXN], col[MAXN], naso[MAXN];
vector <int> v, g[MAXN];

void comp1 () {
    for (int i=1; i<=n; i++) {
        if (!bio[i]) {
            v.push_back(i);
            for (int j=1; j<=n; j++) {
                if (a[i][j] == 1) bio[j] = i;
            }
        }
    }
}

int nadi (int x) {
    if (x == par[x]) return x;
    return par[x] = nadi(par[x]);
}

void spoji (int x, int y) {
    int px = nadi(x), py = nadi(y);
    if (px == py) return;
    par[py] = px;
    g[x].push_back(y);
    g[y].push_back(x);
}

void comp2 () {
    for (auto x : v) {
        for (auto y : v) {
            if (a[x][y] == 2) spoji(x, y);
        }
    }
}

int curr;

int dfs (int x, int doso) {
    if (doso != 0 && a[curr][x] == a[curr][doso] && !naso[col[x]]) return col[x];
    naso[col[x]]++;
    for (auto sus : g[x]) {
        if (sus != doso && col[sus] != 0) {
            int boja = dfs(sus, x);
            if (boja != 0) return boja;
        }
    }
    naso[col[x]]--;
    return 0;
}

void oboji (int x) {
    if (col[x]) return;
    memset(naso, 0, sizeof naso);
    curr = x;
    int boja = dfs(x, 0);
    if (boja == 0) col[x] = ++cnt; else col[x] = boja;
    for (auto sus : g[x]) {
        oboji(sus);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> tip >> n;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            cin >> a[i][j];
        }
    }
    comp1();
    for (auto x : v) {
        par[x] = x;
    }
    comp2();
    oboji(1);
    for (int i=1; i<=n; i++) {
        cout << col[bio[i]] << " ";
    }
    cout << endl;
    for (int i=1; i<=n; i++) {
        if (bio[i] == i) {
            for (auto sus : g[i]) {
                if (i < sus) cout << i << " " << sus << endl;
            }
        } else {
            cout << i << " " << bio[i] << endl;
        }
    }
    return 0;
}

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