Submission #857751

#	Time	Username	Problem	Language	Result	Execution time	Memory
857751		_uros9	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	227 ms	24208 KiB

supertrees

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

int n;
int N=1e3+9;
vector<int> rnk(N,0),par(N);
int ulp(int node){
    if(par[node]==node) return node;
    return par[node]=ulp(par[node]);
}
void spajaj(int a,int b){
    a=ulp(a);b=ulp(b);
    if(a==b) return;
    if(rnk[b]>rnk[a])
        swap(a,b);
    par[b]=a;
    if(rnk[a]==rnk[b])
        rnk[a]++;
}


int construct(std::vector<std::vector<int>> p){
	n=p.size();
	std::vector<std::vector<int>> answer;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	vector<set<int>> lanci(n);
	for(int i=0; i<n; i++) par[i]=i;
	for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==1)
                spajaj(i,j);
            if(p[i][j]==3) return 0;
        }
	}
	for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]==1){
                lanci[ulp(i)].insert(j);
                lanci[ulp(i)].insert(i);
            }
            if(ulp(i)==ulp(j)&&p[i][j]!=1)
                return 0;
        }
	}
	for(int i=0; i<n; i++){
        if(lanci[i].size()<=1) continue;
        for(auto it=next(lanci[i].begin()); it!=lanci[i].end(); it++){
            answer[*prev(it)][*it]=1;
            answer[*it][*prev(it)]=1;
        }
	}
	vector<int> br_poj_predstavnika(n,0);
	for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(p[i][j]!=2) continue;
            if(br_poj_predstavnika[ulp(i)]==2||br_poj_predstavnika[ulp(j)]==2) continue;
            //cout << i << " " << j << endl;
            br_poj_predstavnika[ulp(i)]++;
            br_poj_predstavnika[ulp(j)]++;
            answer[ulp(i)][ulp(j)]=1;
            answer[ulp(j)][ulp(i)]=1;
        }
	}
	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