oj.uz

Submission #1041635

# Submission time Handle Problem Language Result Execution time Memory
1041635 2024-08-02T06:34:11 Z vjudge1 Izlet (COI19_izlet) C++17
43 / 100
 1000 ms 46420 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e3 + 100;
int n, g, mat[N][N], par[N], col[N], cur_col;
set<int> reps;
vector<int> S[N];
vector<pair<int, int>> edges;
bool edge[N][N];

int root(int v){
    return (par[v] == -1 ? v : par[v] = root(par[v]));
}

void merge(int u, int v){
    if ((u = root(u)) == (v = root(v)))
        return;

    if (S[u].size() > S[v].size())
        swap(u, v);

    edges.push_back({u, v});
    edge[u][v] = edge[v][u] = 1;
    reps.erase(u);
    par[u] = v;
    for (int x : S[u]){
        par[x] = v;
        S[v].push_back(x);
    }
    S[u].clear();
}

int main(){
    cin >> g >> n;
    for (int i = 1; i <= n; i ++){
        par[i] = -1, S[i] = {i};
        reps.insert(i);
    }
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            cin >> mat[i][j];

    if (g == 2){
        col[1] = ++cur_col;
        for (int i = 2; i <= n; i ++){
            for (int j = i - 1; j > 0; j --){
                if (mat[j][i - 1] == mat[j][i]){
                    col[i] = col[j];
                    break;
                }
            }
            if (!col[i])
                col[i] = ++cur_col;
        }

        for (int i = 1; i <= n; i ++)
            cout << col[i] << " ";
        cout << endl;
        for (int i = 1; i < n; i ++)
            cout << i << " " << i + 1 << endl;
        return 0;
    }

    for (int i = 1; i <= n; i ++)
        for (int j = i + 1; j <= n; j ++)
            if (mat[i][j] == 1)
                merge(i, j);

    if (g == 1){
        int p = *reps.begin();
        for (int v : reps){
            col[v] = (p == v) ? 1 : 2;
            for (int x : S[v])
                col[x] = col[v];
            if (p != v) edges.push_back({p, v});
        }
    }

    for (int i = 1; i <= n; i ++)
        cout << col[i] << " ";
    cout << endl;
    for (auto [u, v] : edges)
        cout << u << " " << v << endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 610 ms 42144 KB Output is correct
3 Correct 612 ms 38224 KB Output is correct
4 Correct 644 ms 46420 KB Output is correct
5 Correct 611 ms 46416 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 38056 KB Output is correct
2 Correct 588 ms 37976 KB Output is correct
3 Correct 949 ms 38188 KB Output is correct
4 Correct 1000 ms 38224 KB Output is correct
5 Correct 618 ms 37972 KB Output is correct
6 Correct 728 ms 37972 KB Output is correct
7 Correct 523 ms 33364 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 610 ms 42144 KB Output is correct
3 Correct 612 ms 38224 KB Output is correct
4 Correct 644 ms 46420 KB Output is correct
5 Correct 611 ms 46416 KB Output is correct
6 Correct 584 ms 38056 KB Output is correct
7 Correct 588 ms 37976 KB Output is correct
8 Correct 949 ms 38188 KB Output is correct
9 Correct 1000 ms 38224 KB Output is correct
10 Correct 618 ms 37972 KB Output is correct
11 Correct 728 ms 37972 KB Output is correct
12 Correct 523 ms 33364 KB Output is correct
13 Incorrect 649 ms 46420 KB Integer 0 violates the range [1, 3000]
14 Halted 0 ms 0 KB -