oj.uz

Submission #234279

# Submission time Handle Problem Language Result Execution time Memory
234279 2020-05-23T18:10:07 Z VEGAnn Izlet (COI19_izlet) C++14
0 / 100
 549 ms 36300 KB 
#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 (ans[gl] != 0) return;

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

    if (cnt == a[gl][v]){
        ans[gl] = ans[v];
        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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 549 ms 36300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -