oj.uz

Submission #1041636

# Submission time Handle Problem Language Result Execution time Memory
1041636 2024-08-02T06:35:13 Z vjudge1 Izlet (COI19_izlet) C++17
43 / 100
 986 ms 46508 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];

    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});
        }
    }
    else{
        vector<int> vec;
        for (int x : reps)
            vec.push_back(x);

        col[vec[0]] = ++cur_col;
        for (int i = 1; i < vec.size(); i ++){
            edges.push_back({vec[i - 1], vec[i]});
            bool done = 0;
            for (int j = i - 1; j >= 0; j --){
                if (mat[vec[j]][vec[i - 1]] == mat[vec[j]][vec[i]]){
                    done = 1;
                    col[vec[i]] = col[vec[j]];
                    break;
                }
            }

            if (!done)
                col[vec[i]] = ++cur_col;
        }

        for (int v : vec)
            for (int x : S[v])
                col[x] = col[v];
    }

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

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 1; i < vec.size(); i ++){
      |                         ~~^~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 598 ms 42148 KB Output is correct
3 Correct 621 ms 38228 KB Output is correct
4 Correct 654 ms 46500 KB Output is correct
5 Correct 640 ms 46420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 46416 KB Output is correct
2 Correct 613 ms 46420 KB Output is correct
3 Correct 986 ms 38224 KB Output is correct
4 Correct 986 ms 38228 KB Output is correct
5 Correct 628 ms 46416 KB Output is correct
6 Correct 718 ms 46492 KB Output is correct
7 Correct 550 ms 41812 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 598 ms 42148 KB Output is correct
3 Correct 621 ms 38228 KB Output is correct
4 Correct 654 ms 46500 KB Output is correct
5 Correct 640 ms 46420 KB Output is correct
6 Correct 609 ms 46416 KB Output is correct
7 Correct 613 ms 46420 KB Output is correct
8 Correct 986 ms 38224 KB Output is correct
9 Correct 986 ms 38228 KB Output is correct
10 Correct 628 ms 46416 KB Output is correct
11 Correct 718 ms 46492 KB Output is correct
12 Correct 550 ms 41812 KB Output is correct
13 Incorrect 631 ms 46508 KB Output isn't correct
14 Halted 0 ms 0 KB -