oj.uz

Submission #866197

# Submission time Handle Problem Language Result Execution time Memory
866197 2023-10-25T15:16:30 Z lolismek Connecting Supertrees (IOI20_supertrees) C++14
0 / 100
 1 ms 348 KB 
#include "supertrees.h"
#include <vector>

using namespace std;

const int NMAX = 1000;

vector <int> adj[NMAX + 1];

int par[NMAX + 1];

int Find(int x){
    if(x == par[x]){
        return x;
    }
    return par[x] = Find(par[x]);
}

void Unite(int i, int j){
    i = Find(i);
    j = Find(j);
    par[i] = j;
}

int rep[NMAX + 1];

vector <int> gr[NMAX + 1];

int construct(vector<vector<int>> p) {
	int n = p.size();

    for(int i = 0; i < n; i++){
        par[i] = i;
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i != j && p[i][j] == 1 && Find(i) != Find(j)){
                adj[i].push_back(j);
                adj[j].push_back(i);
                Unite(i, j);
            }
        }
    }

    for(int i = 0; i < n; i++){
        rep[i] = par[i];
        par[i] = i;
    }



    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j] == 2){
                Unite(rep[i], rep[j]);
            }
        }
    }

    for(int i = 0; i < n; i++){
        gr[Find(i)].push_back(i);
    }

    for(int i = 0; i < n; i++){
        if((int)gr[i].size() >= 3){
            for(int j = 1; j < (int)gr[i].size(); j++){
                adj[gr[i][j]].push_back(gr[i][j - 1]);
                adj[gr[i][j - 1]].push_back(gr[i][j]);
            }
            adj[gr[i].back()].push_back(gr[i][0]);
            adj[gr[i][0]].push_back(gr[i].back());
        }else{
            return 0;
        }
    }

    vector <vector <int>> ans(n, vector <int> (n, 0));
    for(int i = 0; i < n; i++){
        for(int x : adj[i]){
            ans[i][x] = 1;
        }
    }

    build(ans);
	return 1;
}

/*
5
1 1 1 2 2
1 1 1 2 2
1 1 1 2 2
2 2 2 1 2
2 2 2 2 1
*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -