oj.uz

Submission #234282

# Submission time Handle Problem Language Result Execution time Memory
234282 2020-05-23T18:16:13 Z VEGAnn Izlet (COI19_izlet) C++14
100 / 100
 828 ms 36600 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];

        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 514 ms 36216 KB Output is correct
3 Correct 511 ms 36064 KB Output is correct
4 Correct 513 ms 35960 KB Output is correct
5 Correct 541 ms 36088 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 36216 KB Output is correct
2 Correct 503 ms 36348 KB Output is correct
3 Correct 824 ms 36600 KB Output is correct
4 Correct 828 ms 36556 KB Output is correct
5 Correct 520 ms 35988 KB Output is correct
6 Correct 513 ms 36092 KB Output is correct
7 Correct 424 ms 30584 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 514 ms 36216 KB Output is correct
3 Correct 511 ms 36064 KB Output is correct
4 Correct 513 ms 35960 KB Output is correct
5 Correct 541 ms 36088 KB Output is correct
6 Correct 588 ms 36216 KB Output is correct
7 Correct 503 ms 36348 KB Output is correct
8 Correct 824 ms 36600 KB Output is correct
9 Correct 828 ms 36556 KB Output is correct
10 Correct 520 ms 35988 KB Output is correct
11 Correct 513 ms 36092 KB Output is correct
12 Correct 424 ms 30584 KB Output is correct
13 Correct 593 ms 36108 KB Output is correct
14 Correct 793 ms 36088 KB Output is correct
15 Correct 480 ms 36088 KB Output is correct
16 Correct 585 ms 36216 KB Output is correct
17 Correct 576 ms 36088 KB Output is correct
18 Correct 506 ms 36212 KB Output is correct
19 Correct 587 ms 36216 KB Output is correct
20 Correct 518 ms 36220 KB Output is correct
21 Correct 546 ms 36088 KB Output is correct
22 Correct 586 ms 36216 KB Output is correct
23 Correct 550 ms 35960 KB Output is correct
24 Correct 603 ms 36216 KB Output is correct
25 Correct 468 ms 36088 KB Output is correct