제출 #1053394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053394		inesfi	슈퍼트리 잇기 (IOI20_supertrees)	C++14	56 / 100	124 ms	35992 KiB

supertrees

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

const int TAILLEMAXI=1002;
int nbpers,couleur,u;
int dejavu[TAILLEMAXI];
int num[TAILLEMAXI];
int nbchem[TAILLEMAXI][TAILLEMAXI];
int vrai[TAILLEMAXI];
vector<int> ec;
vector<int> compo[TAILLEMAXI];
vector<int> un[TAILLEMAXI];
int val[TAILLEMAXI];
int rep[TAILLEMAXI][TAILLEMAXI];
vector<vector<int>> r;
vector<int> deux;
int pos[TAILLEMAXI][TAILLEMAXI];

void dfs1(int n){
    if (dejavu[n]==1){
        return ;
    }
    dejavu[n]=1;
    num[n]=couleur;
    ec.push_back(n);
    for (int i=0;i<nbpers;i++){
        if (nbchem[n][i]>0){
            dfs1(i);
        }
    }
}

void dfs2(int n){
    if (dejavu[n]==1){
        return ;
    }
    dejavu[n]=1;
    vrai[n]=1;
    ec.push_back(n);
    for (int i=0;i<nbpers;i++){
        if (nbchem[n][i]==1){
            dfs2(i);
        }
    }
}

bool verif3(){
    bool pb=false;
    for (int i=0;i<nbpers;i++){
        for (int j=0;j<nbpers;j++){
            if (nbchem[i][j]==3){
                pb=true;
            }
        }
    }
    return pb;
}

int construct(vector<vector<int>> c) {
	nbpers=c.size();
    for (int i=0;i<nbpers;i++){
        for (int j=0;j<nbpers;j++){
            nbchem[i][j]=c[i][j];
        }
    }
    if (verif3()==true){
        return 0;
    }
    for (int i=0;i<nbpers;i++){
        if (dejavu[i]==0){
            ec.clear();
            dfs1(i);
            compo[couleur]=ec;
            couleur++;
        }
    }
    for (int j=0;j<nbpers;j++){
        dejavu[j]=0;
    }
    for (int i=0;i<couleur;i++){
        deux.clear();
        for (int ipers=0;ipers<(int)compo[i].size();ipers++){
            if (dejavu[compo[i][ipers]]==0){
                deux.push_back(compo[i][ipers]);
            }
            ec.clear();
            dfs2(compo[i][ipers]);
            un[compo[i][ipers]]=ec;
            if (ec.size()>1) {
                for (int ilien=0;ilien<(int)un[compo[i][ipers]].size()-1;ilien++){
                    rep[un[compo[i][ipers]][ilien]][un[compo[i][ipers]][ilien+1]]=1;
                    rep[un[compo[i][ipers]][ilien+1]][un[compo[i][ipers]][ilien]]=1;
                }
            }
        }
        /*for (int ideux=0;ideux<(int)deux.size();ideux++){
            for (int iautre=0;iautre<nbpers;iautre++){
                if ()
            }
        }*/
        for (int ideux=0;ideux<(int)deux.size()-1;ideux++){
            rep[deux[ideux]][deux[ideux+1]]=1;
            rep[deux[ideux+1]][deux[ideux]]=1;
        }
        if (deux.size()>2){
            rep[deux[0]][deux[deux.size()-1]]=1;
            rep[deux[deux.size()-1]][deux[0]]=1;
        }
    }
    for (int i=0;i<nbpers;i++){
        ec.clear();
        for (int j=0;j<nbpers;j++){
            if (rep[i][j]==1){
                ec.push_back(1);
            }
            else {
                ec.push_back(0);
            }
        }
        r.push_back(ec);
    }
    for (int ipers=0;ipers<nbpers;ipers++){
        if (un[ipers].size()>1){
            for (int i=0;i<(int)un[ipers].size();i++){
                for (int j=0;j<(int)un[ipers].size();j++){
                    pos[un[ipers][i]][un[ipers][j]]=1;
                }
            }
        }
    }
    for (int i=0;i<nbpers;i++){
        for (int j=0;j<nbpers;j++){
            if (i!=j){
                if (nbchem[i][j]==0 and num[i]==num[j]){
                    //cout<<i<<" "<<j<<endl;
                    //cout<<"un"<<endl;
                    return 0;
                }
                if (nbchem[i][j]==1 and pos[i][j]==0){
                    //cout<<i<<" "<<j<<endl;
                    return 0;
                }
                if (nbchem[i][j]==2 and pos[i][j]==1){
                    return 0;
                }
            }
        }
    }
	build(r);
	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