Submission #1291656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291656		ChuanChen	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	110 ms	22256 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(p[i][j] == 1 && 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] != 1 && find(i) == find(j)){
                if(find(i)==find(j)) return 0;
	        }
        }
    }

	// for(int i = 0; i < n; i++){
    //     for(int j = 0; j < n; j++){
    //         if(find(i) == find(j)){
    //             p[i][j]--;
	//         }
    //     }
    // }

	for(int i = 0; i < n; i++){
		comps[i].clear();
		comps[i].push_back(rep[i]);
	}

	for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(p[i][j] == 2 && 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 && 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;
}

// 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: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4