제출 #790913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790913		alexander707070	슈퍼트리 잇기 (IOI20_supertrees)	C++14	100 / 100	193 ms	36260 KiB

supertrees

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

int n;
int dsu[MAXN],dsu2[MAXN];
vector<int> comp[MAXN],comp2[MAXN];
vector< vector<int> > ans;

int root(int x){
    if(dsu[x]==x)return x;
    dsu[x]=root(dsu[x]);
    return dsu[x];
}

void mergev(int x,int y){
    dsu[root(x)]=root(y);
}

int root2(int x){
    if(dsu2[x]==x)return x;
    dsu2[x]=root2(dsu2[x]);
    return dsu2[x];
}

void mergev2(int x,int y){
    dsu2[root2(x)]=root2(y);
}

void add_edge(int x,int y){
    ans[x][y]=ans[y][x]=1;
}

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

    ans.resize(n);
    for(int i=0;i<n;i++){
        ans[i].resize(n);
    }

    for(int i=0;i<n;i++){
        dsu[i]=dsu2[i]=i;
    }

    for(int i=0;i<n;i++){
        for(int f=i+1;f<n;f++){
            if(p[i][f]==1)mergev(i,f);
            if(p[i][f]==3)return 0;
        }
    }

    for(int i=0;i<n;i++){
        comp[root(i)].push_back(i);
    }

    for(int i=0;i<n;i++){
        if(comp[i].empty())continue;

        for(int f=0;f<comp[i].size();f++){
            for(int k=f+1;k<comp[i].size();k++){
                if(p[comp[i][f]][comp[i][k]]!=1)return 0;
            }
        }
        for(int f=0;f<comp[i].size()-1;f++){
            add_edge(comp[i][f],comp[i][f+1]);
        }
    }

    for(int i=0;i<n;i++){
        for(int f=i+1;f<n;f++){
            if(p[i][f]==2)mergev2(root(i),root(f));
        }
    }

    for(int i=0;i<n;i++){
        if(comp[i].empty())continue;
        comp2[root2(i)].push_back(i);
    }

    for(int i=0;i<n;i++){
        if(comp2[i].empty() or comp2[i].size()==1)continue;
        if(comp2[i].size()==2)return 0;

        for(int f=0;f<comp2[i].size();f++){
            for(int k=f+1;k<comp2[i].size();k++){
                for(int t:comp[comp2[i][f]]){
                    for(int s:comp[comp2[i][k]]){
                        if(p[t][s]!=2)return 0;
                    }
                }
            }
        }
        for(int f=0;f<comp2[i].size();f++){
            add_edge(comp2[i][f],comp2[i][(f+1)%int(comp2[i].size())]);
        }
    }

    build(ans);

    /*
    for(int i=0;i<ans.size();i++){
        for(int f=0;f<ans.size();f++){
            cout<<ans[i][f]<<" ";
        }
        cout<<"\n";
    }
    */
    
    return 1;
}

/*
int main(){
    construct({{1, 1, 1,1}, {1, 1, 1,1}, {1,1,1,1}, {1,1,1,1}});
}
*/

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int f=0;f<comp[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~
supertrees.cpp:62:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for(int k=f+1;k<comp[i].size();k++){
      |                           ~^~~~~~~~~~~~~~~
supertrees.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int f=0;f<comp[i].size()-1;f++){
      |                     ~^~~~~~~~~~~~~~~~~
supertrees.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int f=0;f<comp2[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~~
supertrees.cpp:87:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(int k=f+1;k<comp2[i].size();k++){
      |                           ~^~~~~~~~~~~~~~~~
supertrees.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int f=0;f<comp2[i].size();f++){
      |                     ~^~~~~~~~~~~~~~~~

• 서브태스크 1: 11 / 11
• 서브태스크 2: 10 / 10
• 서브태스크 3: 19 / 19
• 서브태스크 4: 35 / 35
• 서브태스크 5: 21 / 21
• 서브태스크 6: 4 / 4