Submission #400052

#	Time	Username	Problem	Language	Result	Execution time	Memory
400052		pliam	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	254 ms	24064 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

vector<bool> visited;
vector<int> cindex,lindex;
vector<vector<int>> matrix;

int construct(vector<vector<int>> p){
    int N=p.size();
    cindex.resize(N);
    lindex.resize(N);
    visited.resize(N);
    matrix.resize(N);
    for(int i=0;i<N;i++){
        visited[i]=false;
        cindex[i]=i;
        lindex[i]=i;
        matrix[i].resize(N);
        for(int j=0;j<N;j++){
            if(p[i][j]==3) return 0;
        }
    }
    for(int i=0;i<N;i++){
        if(visited[i]) continue;
        visited[i]=true;
        int cycle_size=1;
        int last2=i;
        for(int j=0;j<N;j++){
            if(visited[j] || p[i][j]==0) continue;
            visited[j]=true;
            if(p[i][j]==1){
                matrix[i][j]=matrix[j][i]=1;
                lindex[j]=i;
            }
            if(p[i][j]==2){
                matrix[last2][j]=matrix[j][last2]=1;
                cycle_size++;
                last2=j;
                lindex[j]=j;
                for(int k=0;k<N;k++){
                    if(visited[k]) continue;
                    if(p[j][k]==1){
                        visited[k]=true;
                        lindex[k]=j;
                        cindex[k]=i;
                        matrix[j][k]=matrix[k][j]=1;
                    }
                }
            }
            cindex[j]=i;
        }
        if(cycle_size==2) return 0;
        if(cycle_size!=1) matrix[i][last2]=matrix[last2][i]=1;
    }
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(lindex[i]==lindex[j]){ if(p[i][j]!=1) return 0;}
            else if(cindex[i]==cindex[j]) {if(p[i][j]!=2) return 0;}
            else if(p[i][j]!=0) return 0;
        }
    }
    build(matrix);
    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