제출 #1284578

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

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
/**ifstream fin ("date.in");
ofstream fout ("date.out");
#define cin fin
#define cout fout**/

const int MAXN=1010;

/**void build (vector <vector <int>> b){
    int n=b.size ();
    for (int i=0;i<n;++i){
        for (int j=0;j<n;++j){
            cout <<b[i][j]<<' ';
        }
        cout <<'\n';
    }
}**/

int n,maxx,tata[MAXN];
bool v[MAXN];
vector <int> crt;
vector <vector <int>> rez,p;

void dfs (int node){
    v[node]=1;
    crt.push_back (node);
    for (int i=0;i<n;++i){
        if (i!=node and p[node][i] and v[i]==0){
            maxx=max (maxx,p[node][i]);
            dfs (i);
        }
    }
}

int construct (vector <vector <int>> aux){
    p=aux;
    n=p.size ();

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

    rez.resize (n, vector <int> (n,0));
    for (int i=0;i<n;++i){
        if (v[i]==0){
            ///am o componenta conexa noua pe care o rezolv
            crt.clear ();
            maxx=0;
            dfs (i);

            if (maxx==0) continue;///am un nod izolat
            if (maxx==1){
                ///verific ca de la fiecare la fiecare sa am 1
                for (auto x:crt){
                    for (auto y:crt){
                        if (p[x][y]==0) return 0;
                    }
                }
                ///am un lant
                for (int j=0;j<crt.size ()-1;++j){
                    rez[crt[j]][crt[j+1]]=1;
                    rez[crt[j+1]][crt[j]]=1;
                }
            }
            else{
                for (auto x:crt){
                    for (auto y:crt){
                        if (p[x][y]==0) return 0;
                    }
                }

                for (auto x:crt){
                    if (tata[x]!=-1) continue;

                    for (auto y:crt){
                        if (y==x) continue;
                        if (p[x][y]==2) continue;
                        if (tata[y]!=-1) return 0;
                        tata[y]=x;
                    }
                }
                vector <int> v;
                for (auto x:crt){
                    if (tata[x]==-1) v.push_back (x);
                    else{
                        rez[x][tata[x]]=1;
                        rez[tata[x]][x]=1;
                    }
                }
                for (int i=0;i<v.size ();++i){
                    int ni=(i+1)%v.size ();
                    rez[v[i]][v[ni]]=1;
                    rez[v[ni]][v[i]]=1;
                }
            }
        }
    }
    build (rez);
    return 1;
}

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