oj.uz

Submission #1041630

# Submission time Handle Problem Language Result Execution time Memory
1041630 2024-08-02T06:30:20 Z vjudge1 Izlet (COI19_izlet) C++17
18 / 100
 614 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];

    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 = 0; j < i; 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;
    if (g == 2){
        for (int i = 1; i < n; i ++)
            cout << i << " " << i + 1 << endl;
        return 0;
    }
    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 2396 KB Output is correct
2 Correct 609 ms 42148 KB Output is correct
3 Correct 609 ms 38044 KB Output is correct
4 Correct 599 ms 46420 KB Output is correct
5 Correct 614 ms 46236 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 609 ms 42148 KB Output is correct
3 Correct 609 ms 38044 KB Output is correct
4 Correct 599 ms 46420 KB Output is correct
5 Correct 614 ms 46236 KB Output is correct
6 Incorrect 601 ms 46420 KB Output isn't correct
7 Halted 0 ms 0 KB -