제출 #768203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768203		ZeroCool	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	172 ms	28076 KiB

supertrees

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

using namespace std;

const int mxn = 1005;

vector<int> g[mxn];
vector<int> comp;
bool vis[mxn];

struct DSU{
    
    int sz[mxn];
    int g[mxn];

    DSU(int n){
        for(int i = 0 ;i<n;i++){
            sz[i] = 1;
            g[i] = i;
        }
    }

    int find(int x){
        if(x == g[x])return x;
        return g[x] = find(g[x]);
    }

    bool unite(int a,int b){
        a = find(a);
        b = find(b);
        if(a == b)return false;

        if(sz[a] > sz[b])swap(a,b);

        g[a] = b;
        sz[b] += sz[a];
        return true;
    }

	inline bool same(int a,int b){
		return find(a) == find(b);
	}
};
  
void dfs(int x){
    vis[x] = true;
    comp.push_back(x);
    for(auto y : g[x]){
        if(vis[y])continue;
        dfs(y);
    }
}

int construct(vector<vector<int>> p) {


	int n = p.size();
	
	DSU d(n);

	vector<vector<int> > ans(n,vector<int>(n,0));

	

	for(int i = 0;i<n;i++){
		for(int j = i+1;j<n;j++){
			//ans[i][j] = ans[j][i] = 0;
			if(p[i][j] == 3)return 0;
			if(p[i][j] == 1)d.unite(i,j);
		}
	}

	for(int i = 0;i<n;i++){
		for(int j = i+1;j<n;j++){
			if(d.same(i,j) && p[i][j] == 0)return 0;
		}
	}

	for(int i = 0;i<n;i++){
		if(d.find(i) != i){
			ans[i][d.find(i)] = ans[d.find(i)][i] = 1;
		}
	}

	for(int i = 0;i<n;i++){
		for(int j = i+1;j<n;j++){
			if(p[i][j] == 2 && d.find(i) == i && d.find(j) == j){
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	}

	for(int i = 0;i<n;i++){
		if(vis[i] || d.find(i) != i)continue;

		comp.clear();
		dfs(i);

		if(comp.size() == 2)return 0;

		for(auto x : comp){
			for(auto y : comp){
				if(x != y && p[x][y] != 2)return 0;
			}
		}

		int sz = comp.size();

		for(int j = 0;j<sz-1;j++){
			ans[comp[j]][comp[j+1]] = ans[comp[j+1]][comp[j]] = 1;
		}

		if(sz != 1)ans[comp[0]][comp.back()] = ans[comp.back()][comp[0]] = 1;
	}
	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