Submission #434661

#	Time	Username	Problem	Language	Result	Execution time	Memory
434661		79brue	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	295 ms	26692 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

struct unionFind{
    int par[1002];
    void init(int n){
        for(int i=0; i<n; i++) par[i] = i;
    }
    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }
    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} uf1, uf2;

int n;
int mat[1002][1002];
vector<vector<int> > ans;
vector<int> degreeTwos[1002];
bool inCycle[1002];
int oneRoot[1002];

int construct(vector<vector<int>> _p){
	int n = _p.size();
	uf1.init(n);
	uf2.init(n);
	for(int i=0; i<n; i++) oneRoot[i] = -1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            mat[i][j] = _p[i][j];
            if(mat[i][j] == 3) return 0;

            if(mat[i][j] == 1) uf1.merge(i, j);
            if(mat[i][j] == 1 || mat[i][j] == 2) uf2.merge(i, j);
        }
    }

    ans.resize(n);
    for(int i=0; i<n; i++) ans[i].resize(n);

    /// 트리 만들기
    for(int i=0; i<n; i++){
        if(i != uf1.find(i)) continue;
        for(int j=0; j<n; j++){
            if(i == uf1.find(j) && j != i) ans[i][j] = ans[j][i] = 1;
        }
        degreeTwos[uf2.find(i)].push_back(i);
    }

    /// 사이클 만들기
    for(int i=0; i<n; i++){
        if(i != uf2.find(i) || (int)degreeTwos[i].size() <= 1) continue;
        if((int)degreeTwos[i].size() == 2) return 0;
        for(int j = 0; j < (int)degreeTwos[i].size() - 1; j++){
            ans[degreeTwos[i][j]][degreeTwos[i][j+1]] = 1;
            ans[degreeTwos[i][j+1]][degreeTwos[i][j]] = 1;
        }
        ans[degreeTwos[i].front()][degreeTwos[i].back()] = 1;
        ans[degreeTwos[i].back()][degreeTwos[i].front()] = 1;
    }

    /// 올바른지 확인하기
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(uf1.find(i) == uf1.find(j)){
                if(mat[i][j] != 1) return 0;
            }
            else if(uf2.find(i) == uf2.find(j)){
                if(mat[i][j] != 2) return 0;
            }
            else{
                if(mat[i][j] != 0) return 0;
            }
        }
    }

    build(ans);
    return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4