Submission #1291792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291792		lucasdmy	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	121 ms	26140 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]++;
    answer[p][x]++;
    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]++;
            answer[k][x]++;
            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]++;
            answer[l][k]++;
        }
    }
    for(int k=0;k<n;k++){
        answer[k][k]=0;
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            if(answer[k][i]>1){
                return 0;
            }
        }
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            if(p[k][i]==0){
                if(comp[k]==comp[i]){
                    return 0;
                }
            }else if(p[k][i]==1){
                if(comp[k]!=comp[i] or branch[k]!=branch[i]){
                   return 0;
                }
            }else{
                if(branch[k]==branch[i]){
                    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: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 0 / 4