Submission #1201067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201067		AzeTurk810	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	0 ms	328 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>

struct DSU {
    std::vector<int> par;
    int n , components;

    DSU(int _n) {
        n = _n;
        components = n;
        par.assign(n , -1);
    }

    int Find(int u) {
        if(par[u] < 0 ) return u;
        return par[u] = Find(par[u]);
    }

    bool Union(int u , int v) {
        u = Find(u);
        v = Find(v);
        if(u != v) {
            components--;
            if(par[u] > par[v]) {
                par[v] += par[u];
                par[u] = v;
                return true;
            }
            par[u] += par[v];
            par[v] = u;
            return true;
        } else {
            return false;
        }
    }
};

int cntt;
std::vector<std::vector<int>> g;
std::vector<bool> used;
std::vector<std::vector<int>> answer;

void dfs(int v , int &ff) {
	used[v] = true;
	cntt++;
	for(auto to : g[v]) {
		if(!used[to]) {
			answer[v][to] = true;
			answer[to][v] = true;
			dfs(to , ff);
			return ;
		}
	}
	if(v != ff) {
		answer[v][ff] = true;
		answer[ff][v] = true;
	}
}


int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if(p[i][j] != p[j][i]) return false;
		}
		
	}
	
	used.assign(n , false);
	g.resize(n);
	answer.assign(n , std::vector<int>(n , false));
	DSU t(n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if(p[i][j]) {
				t.Union(i , j);
				g[i].push_back(j);
			}
		}
		
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if(!p[i][j]) {
				if(t.Find(i) == t.Find(j)) return false;
			}
		}
		
	}
	for (int i = 0; i < n; i++)
	{
		if(!used[i] && p[i][i]) {
			cntt = 0;
			dfs(i , i);
			// if(cntt <= 1) {
			// 	return false;
			// }
		} else {
			int cntt = -t.par[t.Find(i)];
			if(!used[i] && cntt > 1) {
				return false;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if(answer[i][j] != answer[j][i]) return false;
		}
		
	}
	
	
	build(answer);
	return 1;
}
/*
4
2 0 2 2 
2 0 2 2
2 2 2 2
0 0 0 0

3
2 2 2
2 2 2
2 2 2

3
2 2 0
2 2 0
0 0 0
*/

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