Submission #348393

#	Time	Username	Problem	Language	Result	Execution time	Memory
348393		Chaska	Connecting Supertrees (IOI20_supertrees)	C++17	46 / 100	253 ms	24300 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> g[1005];
bool vs[1005],y;
int dad[1005],ran[1005];
bool VS[1005];

int bus(int u)
{
    if (dad[u] != u) dad[u] = bus(dad[u]);
    return dad[u];
}
void unir(int u,int v)
{
    u = bus(u); v = bus(v);
    if (u != v) {
        if (ran[u]>ran[v]) dad[v] = u;
        else if (ran[v] > ran[u]) dad[u] = v;
        else {
            ran[u]++;
            dad[v] = u;
        }
    }
}
int construct(std::vector<std::vector<int>> p) {
	int 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);
	}
    for (int i=0;i<n;i++) {
        dad[i] = i;
    }
     y= true;
    for (int i=0;i<n;i++) if (!VS[i]) {
        for (int j=0;j<n;j++) if (i != j) {
            if (p[i][j]==1) {
                if (bus(i) != bus(j)) {
                answer[i][j] = 1;
                answer[j][i] = 1;
                VS[j] = true;
                unir(i,j);
                }
            }
        }
    }
    for (int i=0;i<n;i++) VS[i] = false;
    for (int i=0;i<n;i++) if (!VS[i]) {
        set<int> s ;
        s.clear();
        s.insert(bus(i));
        for (int  j=0;j<n;j++) if (p[i][j]==2) {
            VS[j] = true;
            s.insert(bus(j));
        }
        vector<int> x ;
        x.clear();
        for (int u : s) x.pb(u);
        int xx = x.size();
        if (xx<3) {
        } else {
            for (int j=0;j<xx-1;j++) {
                answer[bus(x[j])][bus(x[j+1])] = 1;
                answer[bus(x[j+1])][bus(x[j])] = 1;
            }
            answer[bus(x[0])][bus(x[xx-1])] = 1;
             answer[bus(x[xx-1])][bus(x[0])] = 1;
     
                
        }
    }
	if (y) build(answer);
	if (y) return 1;
    else return 0;
}

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