Submission #1200488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200488		AzeTurk810	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	130 ms	26060 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;

        }

    }

};



std::vector<int> used;

std::vector<std::vector<int>> g;

std::vector<std::vector<int>> answer;



void dfs(int v) {

    used[v] = true;

    for(int &to : g[v]) {

        if(!used[to]) {

			answer[v][to] = true;

			answer[to][v] = true;

            dfs(to);		

		}

    }

}



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

	int n = p.size();

	used.assign(n , false);

	g.resize(n);

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < n; j++) {

			if(p[i][j] != p[j][i]) return false;

		}

	}

	

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < n; j++) {

			if(p[i][j]) {

				g[i].push_back(j);

			}

		}

	}

	answer.assign(n , std::vector<int> (n , false));

	for (int i = 0; i < n; i++)

	{

		if(!used[i]) {

			dfs(i);

		}

	}

	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);

		}

		

	}

	for (int i = 0; i < n; i++) {

		for (int j = 0; j < n; j++) {

			if(!p[i][j]) {

				// std::cerr << i << ':' << j << std::endl;

				if(t.Find(i) == t.Find(j)) return false;

			}

		}

		

	}

	

	build(answer);

	return 1;

}

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