제출 #1291787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291787		lucasdmy	슈퍼트리 잇기 (IOI20_supertrees)	C++20	56 / 100	118 ms	26144 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
vector<vector<int>>answer, v;
vector<int>marc(MAXN), branch(MAXN), comp(MAXN);
int n, l, c=0;
void dfs(int x, int p){
    answer[x][p]=1;
    answer[p][x]=1;
    marc[x]=1;
    comp[x]=c;
    branch[x]=x;
    l=x;
    for(int k=0;k<n;k++){
        if(v[x][k]==1 and marc[k]==0){
            answer[x][k]=1;
            answer[k][x]=1;
            marc[k]=1;
            comp[k]=c;
            branch[k]=x;
        }
    }
    for(int k=0;k<n;k++){
        if(v[x][k]==2 and marc[k]==0){
            dfs(k, x);
        }
    }
}
/*void build(vector<vector<int>>p){
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            cout<<p[k][i]<<' ';
        }
        cout<<endl;
    }
}*/
int construct(vector<vector<int>>p){
	n=p.size();
    v=p;
    for(int k=0;k<n;k++){
		vector<int>row;
		row.resize(n);
		answer.push_back(row);
	}
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            answer[k][i]=0;
        }
    }
    for(int k=0;k<n;k++){
        if(marc[k]==0){
            c++;
            dfs(k, k);
            answer[k][l]=1;
            answer[l][k]=1;
        }
    }
    for(int k=0;k<n;k++){
        answer[k][k]=0;
    }
    int ok=true;
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            if(p[k][i]==0){
                if(comp[k]==comp[i]){
                    ok=false;
                    break;
                }
            }else if(p[k][i]==1){
                if(comp[k]!=comp[i] or branch[k]!=branch[i]){
                    ok=false;
                    break;
                }
            }else{
                if(comp[k]!=comp[i] or branch[k]==branch[i]){
                    ok=false;
                    break;
                }
            }
        }
        if(!ok){
            break;
        }
    }
    if(!ok){
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                answer[k][i]=0;
            }
        }
        return 0;
    }
	build(answer);
	return 1;
}
/*int main(){
    cin>>n;
    vector<vector<int>>in(n, vector<int>(n));
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            cin>>in[k][i];
        }
    }
    cout<<construct(in);
}*/

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