Submission #866196

#	Time	Username	Problem	Language	Result	Execution time	Memory
866196		lolismek	Connecting Supertrees (IOI20_supertrees)	C++14	46 / 100	143 ms	24400 KiB

supertrees

#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());
        }
    }

    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: 11 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4