Submission #471250

#	Time	Username	Problem	Language	Result	Execution time	Memory
471250		Cross_Ratio	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	269 ms	22208 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;
vector<vector<int> > adj2;
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 UF1(N);
	UnionFind UF2(N);
	adj.resize(N);
	adj2.resize(N);
	for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
            if(p[i][j]==1) {
                UF2.Merge(i, j);
            }
            if(p[i][j]) {
                UF1.Merge(i, j);
            }
            if(p[i][j]==3) return 0;
        }
	}
	for(i=0;i<N;i++) {
        for(j=0;j<N;j++) {
            if(!p[i][j]) {
                if(UF1.Find(i)==UF1.Find(j)) return 0;
                if(UF2.Find(i)==UF2.Find(j)) return 0;
            }
            if(p[i][j] == 2) {
                if(UF2.Find(i)==UF2.Find(j)) return 0;
            }
        }
	}
	for(i=0;i<N;i++) {
        adj2[UF2.Find(i)].push_back(i);
	}
	for(i=0;i<N;i++) {
        if(!adj2[i].empty()) {
            //cout << adj2[i][0] << ' ';
            adj[UF1.Find(adj2[i][0])].push_back(adj2[i][0]);
        }
	}
	for(i=0;i<N;i++) {
        int sz = adj[i].size();
        //if(sz == 1) return 0;
        if(sz == 2) return 0;
        if(sz >= 3) {
            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;
        }
        int sz2 = adj2[i].size();
        for(j=0;j<sz2-1;j++) {
            ans[adj2[i][j]][adj2[i][j+1]] = 1;
            ans[adj2[i][j+1]][adj2[i][j]] = 1;
        }
	}
	build(ans);
	return 1;
}

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