Submission #471155

#	Time	Username	Problem	Language	Result	Execution time	Memory
471155		Cross_Ratio	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	272 ms	24172 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;

//void build(vector<vector<int> >);

struct UnionFind {
    vector<int> root;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int a) {
        if(root[a] < 0) return a;
        int r = Find(root[a]);
        root[a] = r;
        return r;
    }
    void Merge(int a, int b) {
        a = Find(a);
        b = Find(b);
        if(a == b) return;
        if(root[a] > root[b]) swap(a, b);
        root[a] += root[b];
        root[b] = a;
    }
};

int construct(vector<vector<int> > p) {
	vector<vector<int> > ans;
	int N = p.size();
	ans.resize(N);
	int i;
	for(i=0;i<N;i++) ans[i].resize(N);
	int j;
	UnionFind UF(N);
	for(i=0;i<N;i++) {
        for(j=0;j<i;j++) {
            if(p[i][j]) {
                ans[i][UF.Find(j)] = 1;
                ans[UF.Find(j)][i] = 1;
                UF.Merge(i, j);
            }
        }
	}
	for(i=0;i<N;i++) {
        for(j=0;j<i;j++) {
            if(!p[i][j]) {
                if(UF.Find(i)==UF.Find(j)) return 0;
            }
        }
	}
	build(ans);
	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