Submission #432099

#	Time	Username	Problem	Language	Result	Execution time	Memory
432099		Platanito_Frito	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	258 ms	22084 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#include <vector>
#define pb push_back

using namespace std;

void dfs(int a, int cl, vector<bool>& mk, vector<int>& scc, vector<int> v[], vector<vector<int>>& answer){
    mk[a]=true;
    scc[a]=cl;
    for(auto b:v[a]){
        if(!mk[b]){ answer[a][b]=answer[b][a]=1; dfs(b, cl, mk, scc, v, answer); }
    }
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
    vector<int> scc(n), v[n];
    vector<bool> mk(n, 0);
    vector<vector<int>> answer;

	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	bool ans=true;

    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            if(i==j) continue;
            if(p[i][j]==1&&!mk[j]){
                v[i].pb(j);
                v[j].pb(i);
                mk[j]=true;
            }
        }
    }

    for(int i=0; i<n; i++) mk[i]=0;

    int id=0;
    for(int i=0; i<n; i++){
        if(!mk[i]){ dfs(i, id, mk, scc, v, answer); id++; }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if((p[i][j]==1&&scc[i]!=scc[j])||(p[i][j]==0&&scc[i]==scc[j])) ans=false;
        }
    }

	if(ans) build(answer);
	return ans;
}

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