Submission #1106022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106022		snpmrnhlol	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	181 ms	28232 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
const int N = 1e3;
vector <int> e[N];
bool vis[N];
bool vis2[N];
vector <int> comp;
vector <int> cycle;
vector <int> comp2;
void dfs(int node){
    vis[node] = 1;
    comp.push_back(node);
    for(auto i:e[node]){
        if(!vis[i]){
            dfs(i);
        }
    }
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> ans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		ans.push_back(row);
	}
	for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            if(p[i][j] && i != j){
                e[i].push_back(j);
            }
        }
	}
	bool ok = 1;
	for(int i = 0;i < n;i++){
        if(!vis[i]){
            comp.clear();
            dfs(i);
            bool de = 0;
            for(auto j:comp){
                for(auto k:comp){
                    if(p[j][k] == 2)de = 1;
                }
            }
            ///can exist double edge or not
            if(de == 0){
                ///create a tree
                for(auto j:comp){
                    ans[j][comp[0]] = 1;
                    ans[comp[0]][j] = 1;
                }
                ans[comp[0]][comp[0]] = 0;
                for(auto j:comp){
                    for(auto k:comp){
                        if(p[j][k] != 1)ok = 0;
                    }
                }
            }else{
                ///create a single cactus
                cycle.clear();
                for(auto j:comp){
                    if(vis2[j])continue;
                    vis2[j] = 1;
                    comp2.clear();
                    comp2.push_back(j);
                    for(auto k:comp){
                        if(vis2[k])continue;
                        if(p[j][k] == 1){
                            vis2[k] = 1;
                            comp2.push_back(k);
                        }
                    }
                    for(auto k:comp2){
                        for(auto q:comp2){
                            if(p[k][q] != 1)ok = 0;
                        }
                    }
                    for(auto k:comp2){
                        for(auto q:comp){
                            if(vis2[q])continue;
                            if(p[k][q] != 2)ok = 0;
                        }
                    }
                    for(int k = 0;k < (int)comp2.size() - 1;k++){
                        ans[comp2[k]][comp2[k + 1]] = 1;
                        ans[comp2[k + 1]][comp2[k]] = 1;
                    }
                    cycle.push_back(comp2[0]);
                }
                if(cycle.size() < 3)ok = 0;
                for(int k = 0;k < (int)cycle.size();k++){
                    ans[cycle[k]][cycle[(k + 1)%(int)cycle.size()]] = 1;
                    ans[cycle[(k + 1)%(int)cycle.size()]][cycle[k]] = 1;
                }
            }
            for(auto j:comp){
                for(int i = 0;i < n;i++){
                    if(vis[i])continue;
                    if(p[j][i] >= 1)ok = 0;
                }
            }
        }
    }
    if(!ok)return 0;
	build(ans);
	return 1;
}
/**
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 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