oj.uz

Submission #117391

# Submission time Handle Problem Language Result Execution time Memory
117391 2019-06-15T19:25:24 Z keko37 Izlet (COI19_izlet) C++14
100 / 100
 744 ms 53712 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 534 ms 37080 KB Output is correct
3 Correct 537 ms 37160 KB Output is correct
4 Correct 499 ms 36984 KB Output is correct
5 Correct 516 ms 40916 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 53712 KB Output is correct
2 Correct 519 ms 36964 KB Output is correct
3 Correct 671 ms 39544 KB Output is correct
4 Correct 699 ms 39392 KB Output is correct
5 Correct 502 ms 37036 KB Output is correct
6 Correct 554 ms 37464 KB Output is correct
7 Correct 395 ms 31608 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 534 ms 37080 KB Output is correct
3 Correct 537 ms 37160 KB Output is correct
4 Correct 499 ms 36984 KB Output is correct
5 Correct 516 ms 40916 KB Output is correct
6 Correct 503 ms 53712 KB Output is correct
7 Correct 519 ms 36964 KB Output is correct
8 Correct 671 ms 39544 KB Output is correct
9 Correct 699 ms 39392 KB Output is correct
10 Correct 502 ms 37036 KB Output is correct
11 Correct 554 ms 37464 KB Output is correct
12 Correct 395 ms 31608 KB Output is correct
13 Correct 744 ms 37088 KB Output is correct
14 Correct 622 ms 37680 KB Output is correct
15 Correct 500 ms 37000 KB Output is correct
16 Correct 585 ms 37372 KB Output is correct
17 Correct 566 ms 37500 KB Output is correct
18 Correct 511 ms 37112 KB Output is correct
19 Correct 575 ms 36984 KB Output is correct
20 Correct 535 ms 36960 KB Output is correct
21 Correct 505 ms 36984 KB Output is correct
22 Correct 516 ms 36984 KB Output is correct
23 Correct 527 ms 36984 KB Output is correct
24 Correct 572 ms 37496 KB Output is correct
25 Correct 493 ms 36984 KB Output is correct