oj.uz

답안 #790906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790906 2023-07-23T09:21:02 Z alexander707070 슈퍼트리 잇기 (IOI20_supertrees) C++14
0 / 100
 7 ms 14292 KB 
#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);
        }
    }

    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;

        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())]);
        }
    }

    for(int i=0;i<n;i++){
        for(int f=i+1;f<n;f++){
            if(root2(root(i))!=root2(root(f)) and p[i][f]!=0)return 0;
            if(root2(root(i))==root2(root(f)) and p[i][f]!=2)return 0;
        }
    }

    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}});
}
*/

Compilation message

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

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 6 ms 14292 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 6 ms 14292 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 6 ms 14292 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Incorrect 6 ms 14292 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Incorrect 7 ms 14292 KB Answer gives possible 0 while actual possible 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 6 ms 14292 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 6 ms 14292 KB Answer gives possible 0 while actual possible 1
3 Halted 0 ms 0 KB -