Submission #418839

#	Time	Username	Problem	Language	Result	Execution time	Memory
418839		qwerasdfzxcl	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	272 ms	24004 KiB

supertrees

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

using namespace std;
typedef long long ll;
int col[1010];
bool visited[1010];

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer, C;
	answer.resize(n);
	for (int i=0;i<n;i++) answer[i].resize(n, 0);

	bool valid0 = 1;
	for (int i=0;i<n;i++){
        for (int j=0;j<n;j++) if (p[i][j]==3) valid0 = 0;
	}
	if (!valid0) return 0;

    for (int i=0;i<n;i++) if (!visited[i]){
        visited[i] = 1;
        vector<int> tmp;
        C.push_back(tmp);
        C.back().push_back(i);
        col[i] = C.size();
        for (int j=0;j<n;j++) if (!visited[j] && p[i][j]){
            C.back().push_back(j);
            col[j] = C.size();
            visited[j] = 1;
        }
    }

    bool valid1 = 1;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (i==j) valid1 &= (p[i][j]==1);
            else if (col[i]==col[j]) valid1 &= (p[i][j]>0);
            else valid1 &= (p[i][j]==0);
        }
    }
    if (!valid1) return 0;

    for (auto &V:C){
        vector<vector<int>> C1;
        vector<int> col1(1010, 0);
        fill(visited, visited+1010, 0);
        for (auto &x:V) if (!visited[x]){
            visited[x] = 1;
            vector<int> tmp;
            C1.push_back(tmp);
            C1.back().push_back(x);
            col1[x] = C1.size();
            for (int j=0;j<n;j++) if (col[j]==col[x] && !visited[j] && p[x][j]==1){
                C1.back().push_back(j);
                visited[j] = 1;
                col1[j] = C1.size();
            }
        }

        bool valid2 = 1;
        for (auto &x:V){
            for (auto &y:V){
                if (col1[x]==col1[y]) valid2 &= (p[x][y]==1);
                else valid2 &= (p[x][y]==2);
            }
        }
        if (!valid2) return 0;
        if ((int)C1.size()==2) return 0;

        for (int i=0;i<(int)C1.size()-1;i++){
            answer[C1[i][0]][C1[i+1][0]] = 1;
            answer[C1[i+1][0]][C1[i][0]] = 1;
        }
        if ((int)C1.size()>1){
            answer[C1.back()[0]][C1[0][0]] = 1;
            answer[C1[0][0]][C1.back()[0]] = 1;
        }
        for (auto &U:C1){
            for (int i=1;i<(int)U.size();i++){
                answer[U[0]][U[i]] = 1;
                answer[U[i]][U[0]] = 1;
            }
        }

    }
	build(answer);
	return 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