제출 #746074

#제출 시각아이디문제언어결과실행 시간메모리
746074JakobZorz슈퍼트리 잇기 (IOI20_supertrees)C++14
21 / 100
205 ms27924 KiB
#include "supertrees.h" #include <vector> using namespace std; vector<vector<int>> answer; int group_ids[1000]; vector<int> groups[1000]; vector<vector<int>> p; int num_groups; void connect(int a, int b){ answer[a][b]=1; answer[b][a]=1; } void connect_group(int group_id){ vector<int> group=groups[group_id]; vector<bool> in_cycle(group.size(),false); int present2=-1; for(int i=0;i<group.size();i++){ for(int j=0;j<group.size();j++){ if(p[group[i]][group[j]]==2){ present2=j; } } } if(present2==-1){ for(int i=0;i<group.size()-1;i++){ connect(group[i],group[i+1]); } return; } vector<int> cycle; in_cycle[present2]=true; for(int i=0;i<group.size();i++){ bool valid=true; for(int j=0;j<cycle.size();j++){ if(p[group[cycle[j]]][group[i]]!=2){ valid=false; break; } } if(valid){ cycle.push_back(i); in_cycle[i]=true; } } for(int i=0;i<cycle.size()-1;i++) connect(group[cycle[i]],group[cycle[i+1]]); connect(group[cycle[0]],group[cycle.back()]); for(int i=0;i<group.size();i++){ if(in_cycle[i]) continue; for(int j=0;j<group.size();j++){ if(i!=j&&p[group[i]][group[j]]==1&&in_cycle[group[j]]){ connect(group[i],group[j]); } } } } int construct(vector<vector<int>> p_) { p=p_; int n = p.size(); answer=vector<vector<int>>(n,vector<int>(n,0)); for(vector<int>& i:p) for(int j:i) if(j==3) return 0; for(int i=0;i<n;i++) group_ids[i]=-1; for(int i=0;i<n;i++){ if(group_ids[i]!=-1) continue; group_ids[i]=num_groups; groups[num_groups].push_back(i); for(int j=i+1;j<n;j++){ if(p[i][j]!=0){ group_ids[j]=num_groups; groups[num_groups].push_back(j); } } num_groups++; } for(int i=0;i<n;i++) for(int j=i+1;j<n;j++){ if(group_ids[i]!=group_ids[j]&&p[i][j]!=0) return 0; if(group_ids[i]==group_ids[j]&&p[i][j]==0) return 0; } for(int i=0;i<num_groups;i++) connect_group(i); build(answer); return 1; }

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

supertrees.cpp: In function 'void connect_group(int)':
supertrees.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<group.size();i++){
      |                 ~^~~~~~~~~~~~~
supertrees.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int j=0;j<group.size();j++){
      |                     ~^~~~~~~~~~~~~
supertrees.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for(int i=0;i<group.size()-1;i++){
      |                     ~^~~~~~~~~~~~~~~
supertrees.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<group.size();i++){
      |                 ~^~~~~~~~~~~~~
supertrees.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j=0;j<cycle.size();j++){
      |                     ~^~~~~~~~~~~~~
supertrees.cpp:52:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0;i<cycle.size()-1;i++)
      |                 ~^~~~~~~~~~~~~~~
supertrees.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<group.size();i++){
      |                 ~^~~~~~~~~~~~~
supertrees.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int j=0;j<group.size();j++){
      |                     ~^~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:101:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  101 |     for(int i=0;i<num_groups;i++)
      |     ^~~
supertrees.cpp:104:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  104 |  build(answer);
      |  ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...