Submission #1291640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291640		ChuanChen	Connecting Supertrees (IOI20_supertrees)	C++20	19 / 100	100 ms	22112 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define debug(v) cout << #v << ": " << v << endl;

const int MAXN = 1e3+3;

int n;
vector<vector<int>> ans;

int rep[MAXN];
vector<int> comps[MAXN];
int find(int no){
    if(rep[no] == no) return no;
    return rep[no] = find(rep[no]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if(comps[a].size() < comps[b].size()) swap(a, b);
    rep[b] = a;
    for(int x : comps[b]) comps[a].push_back(x);
    comps[b].clear();
}

int construct(vector<vector<int>> p) {
	n = p.size();
    ans.assign(n, vector<int>(n, 0));
	for(int i = 0; i < n; i++){
        comps[i].push_back(i);
        rep[i] = i;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j] == 0) continue;
            if(find(i) != find(j)){
                merge(i, j);
                // ans[j][i] = ans[i][j] = 1;
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j] == 0){
                if(find(i)==find(j)) return 0;
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(comps[i].size() == 2) return 0;
        if(comps[i].size() < 2) continue;
        for(int j = 0; j < (int)comps[i].size(); j++)
            ans[comps[i][j]][comps[i][(j+1)%comps[i].size()]] = ans[comps[i][(j+1)%comps[i].size()]][comps[i][j]] = 1;
    }
    build(ans);
    return 1;
}

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