Submission #471160

#	Time	Username	Problem	Language	Result	Execution time	Memory
471160		Cross_Ratio	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	204 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;
    }
};
vector<vector<int> > adj;
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);
	adj.resize(N);
	for(i=0;i<N;i++) {
        for(j=0;j<i;j++) {
            if(p[i][j]==2) {
                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;
            }
        }
	}
	for(i=0;i<N;i++) {
        adj[UF.Find(i)].push_back(i);
	}
	for(i=0;i<N;i++) {
        int sz = adj[i].size();
        //if(sz == 1) return 0;
        if(sz >= 2) {
            for(j=0;j<sz-1;j++) {
                ans[adj[i][j]][adj[i][j+1]] = 1;
                ans[adj[i][j+1]][adj[i][j]] = 1;
            }
            ans[adj[i][0]][adj[i][sz-1]] = 1;
            ans[adj[i][sz-1]][adj[i][0]] = 1;
        }
	}
	build(ans);
	return 1;
}

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