Submission #673462

#	Time	Username	Problem	Language	Result	Execution time	Memory
673462		beedle	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	178 ms	24076 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
using namespace std;

/*
    Disjoint Set Union: Union by rank, size of each component is maintained.

    Usage: dsu(n) -> creates dsu for elements 0 to n-1, with each element as its own component 
           find_set(v) -> as usual 
           union_sets(a,b) -> as usual
           size_containing(v) -> gives size of component containing vertex v
*/

class dsu {
  public:
    vector<int> parent;
    vector<int> size;
    vector<int> rnk;

    dsu(int n) {
        parent.assign(n, 0);
        for (int i = 0; i < n; i++)
            parent[i] = i;
        size.assign(n, 1);
        rnk.assign(n, 0);
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (rnk[a] < rnk[b])
                swap(a, b);
            parent[b] = a;
            if (rnk[a] == rnk[b])
                rnk[a]++;
            size[a] += size[b];
        }
    }

    int size_containing(int a) { return size[find_set(a)]; }
};

int construct(std::vector<std::vector<int>> p) {
	int n = sz(p);
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	dsu d(n);
	rep(i,0,n-1)
	rep(j,0,n-1)
	if(p[i][j]!=0)
	d.union_sets(i,j);

	rep(i,0,n-1)
	rep(j,0,n-1)
	if(p[i][j]==0 && d.find_set(i)==d.find_set(j))
	return 0;

	rep(i,0,n-1)
	rep(j,0,n-1)
	if(p[i][j]==3)
	return 0;

	vector <int> comps[n];
	rep(i,0,n-1)
	comps[d.find_set(i)].push_back(i);

	rep(compno,0,n-1)
	if(sz(comps[compno])>1)
	{
		dsu ds(n);
		int s=sz(comps[compno]);
		rep(i,0,s-1)
		rep(j,0,s-1)
		{
			int v1=comps[compno][i];
			int v2=comps[compno][j];
			if(p[v1][v2]==1)
			ds.union_sets(v1,v2);
		}
		rep(i,0,s-1)
		rep(j,0,s-1)
		{
			int v1=comps[compno][i];
			int v2=comps[compno][j];
			if(p[v1][v2]==2 && ds.find_set(v1)==ds.find_set(v2))
			return 0;
		}
		vector <int> seqs[n];
		for(auto v:comps[compno])
		seqs[ds.find_set(v)].push_back(v);

		vector <int> cntc;
		rep(i,0,n-1)
		if(sz(seqs[i])>0)
		cntc.push_back(i);

		if(sz(cntc)==2)
		return 0;

		rep(i,0,n-1)
		if(sz(seqs[i])>0)
		for(auto x:seqs[i])
		if(x!=i)
		answer[x][i]=answer[i][x]=1;

		s=sz(cntc);
		rep(i,0,s-2)
		{
			int v1=cntc[i];
			int v2=cntc[i+1];
			answer[v1][v2]=answer[v2][v1]=1;
		}
		int v1=cntc[0];
		int v2=cntc[s-1];
		answer[v1][v2]=answer[v2][v1]=1;
	}

	build(answer);
	return 1;
}


// signed main() 
// {
// 	vector <vector<int>> p={{1,1,2,2},{1,1,2,2},{2,2,1,2},{2,2,2,1}};
// 	construct(p);
// 	return 0;
// }

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