oj.uz

Submission #234281

# Submission time Handle Problem Language Result Execution time Memory
234281 2020-05-23T18:14:22 Z VEGAnn Izlet (COI19_izlet) C++14
100 / 100
 792 ms 40856 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 (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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 575 ms 36856 KB Output is correct
3 Correct 545 ms 36860 KB Output is correct
4 Correct 509 ms 36856 KB Output is correct
5 Correct 514 ms 36728 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 36036 KB Output is correct
2 Correct 506 ms 40856 KB Output is correct
3 Correct 777 ms 38776 KB Output is correct
4 Correct 792 ms 38392 KB Output is correct
5 Correct 518 ms 36856 KB Output is correct
6 Correct 524 ms 36800 KB Output is correct
7 Correct 432 ms 31392 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 575 ms 36856 KB Output is correct
3 Correct 545 ms 36860 KB Output is correct
4 Correct 509 ms 36856 KB Output is correct
5 Correct 514 ms 36728 KB Output is correct
6 Correct 573 ms 36036 KB Output is correct
7 Correct 506 ms 40856 KB Output is correct
8 Correct 777 ms 38776 KB Output is correct
9 Correct 792 ms 38392 KB Output is correct
10 Correct 518 ms 36856 KB Output is correct
11 Correct 524 ms 36800 KB Output is correct
12 Correct 432 ms 31392 KB Output is correct
13 Correct 623 ms 36876 KB Output is correct
14 Correct 753 ms 36956 KB Output is correct
15 Correct 471 ms 36728 KB Output is correct
16 Correct 578 ms 36756 KB Output is correct
17 Correct 591 ms 36960 KB Output is correct
18 Correct 505 ms 36740 KB Output is correct
19 Correct 603 ms 36712 KB Output is correct
20 Correct 548 ms 36604 KB Output is correct
21 Correct 585 ms 36616 KB Output is correct
22 Correct 604 ms 36472 KB Output is correct
23 Correct 607 ms 36472 KB Output is correct
24 Correct 584 ms 36472 KB Output is correct
25 Correct 534 ms 36472 KB Output is correct