Submission #627438

#	Time	Username	Problem	Language	Result	Execution time	Memory
627438		ttamx	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	236 ms	23964 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> ans;
vector<int> adj[1005];
int pa[1005];
bool vis[1005];

int fp(int u){
    if(pa[u]==u)return u;
    return pa[u]=fp(pa[u]);
}

void dfs(int u,int p){
    for(auto v:adj[u]){
        if(vis[v])continue;
        vis[v]=1;
        ans[u][v]=1;
        ans[v][u]=1;
        dfs(v,u);
    }
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	for(int i=0;i<n;++i)pa[i]=i;
	for (int i = 0; i < n; i++) {
		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]==3)return 0;
            if(p[i][j]==1){
                pa[fp(i)]=fp(j);
            }
            if(p[i][j]==2){
                adj[i].emplace_back(j);
            }
        }
	}
	for(int i=0;i<n;++i){
        dfs(i,-1);
        if(i==fp(i))continue;
        ans[i][fp(i)]=1;
        ans[fp(i)][i]=1;
	}
	/*
	for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
	}
	*/
	build(ans);
	return 1;
}
/*
int main(){
    int n;
    vector<vector<int>> p;
    cin >> n;
    p.resize(n);
    for(int i=0;i<n;++i){
        p[i].resize(n);
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            cin >> p[i][j];
        }
    }
    construct(p);
}
*/

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