제출 #431204

#제출 시각아이디문제언어결과실행 시간메모리
431204Hazem슈퍼트리 잇기 (IOI20_supertrees)C++14
40 / 100
318 ms34192 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; const int N = 2e3+10; vector<int>adj[N],vec,vec1; vector<vector<int>>adjans,p; int n,vis[N],vis1[N]; void dfs(int i){ if(vis[i]) return ; vis[i] = 1; vec.push_back(i); for(auto x:adj[i]) dfs(x); } void dfs(int i,int t){ if(vis1[i]) return ; vis1[i] = 1; vec1.push_back(i); for(auto x:adj[i]) if(p[i][x]==1) dfs(x,t); } bool checkallequal(vector<int>vec1){ bool ret = 1; for(int i=0;i<vec.size();i++) for(int j=i+1;j<vec.size();j++){ bool q = 0; for(auto x:vec1) q |= p[vec[i]][vec[j]]==x; ret &= q; } return ret; } int construct(std::vector<std::vector<int>> P) { p = P; n = p.size(); adjans = vector<vector<int>>(n,vector<int>(n,0)); int mx = 0,mn = 10;set<int>st; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ if(p[i][j]){ adj[i].push_back(j); adj[j].push_back(i); } mx = max(mx,p[i][j]); mn = min(mn,p[i][j]); if(i!=j) st.insert(p[i][j]); } if(mx<=1){ bool ans = 1; for(int i=0;i<n;i++){ dfs(i);bool q = 1; for(int j=0;j<vec.size();j++) for(int k=0;k<vec.size();k++) q &= p[vec[j]][vec[k]]==1; //q &= !vec.size()||vec.size()>2; for(int j=0;j<(int)vec.size()-1;j++) adjans[vec[j]][vec[j+1]] = adjans[vec[j+1]][vec[j]] = 1; //adjans[vec[0]][vec.back()] = adjans[vec.back()][vec[0]] = 1; vec.clear(); ans &= q; } if(!ans) return 0; build(adjans); return 1; } if((mx==2&&mn==0&&st.size()==2)||(mx==mx&&mx==2)||(!mx)){ bool ans = 1; for(int i=0;i<n;i++){ dfs(i);bool q = 1; if(vec.size()<=1){ vec.clear(); continue; } for(int j=0;j<vec.size();j++) for(int k=j+1;k<vec.size();k++){ q &= p[vec[j]][vec[k]]==2; assert(vec[j]!=vec[k]); } q &= vec.size()>2; for(int j=0;j<(int)vec.size()-1;j++) adjans[vec[j]][vec[j+1]] = adjans[vec[j+1]][vec[j]] = 1; adjans[vec[0]][vec.back()] = adjans[vec.back()][vec[0]] = 1; vec.clear(); ans &= q; } if(!ans) return 0; build(adjans); return 1; } bool ans = 1; for(int i=0;i<n;i++){ dfs(i);bool q = 1; if(vec.size()<=1){ vec.clear(); continue; } vector<int>vec3; for(auto x:vec){ dfs(x,1); for(int j=0;j<(int)vec1.size()-1;j++){ adjans[vec1[j]][vec1[j+1]] = adjans[vec1[j+1]][vec1[j]] = 1; assert(vec1[j]!=vec1[j+1]); } if(vec1.size()) vec3.push_back(x); vec1.clear(); } for(int j=0;j<(int)vec3.size()-1;j++){ adjans[vec3[j]][vec3[j+1]] = adjans[vec3[j+1]][vec3[j]] = 1; assert(vec3[j]!=vec3[j+1]); } if(vec3.size()){ adjans[vec3[0]][vec3.back()] = adjans[vec3.back()][vec3[0]] = 1; assert(vec[0]!=vec3.back()); } } build(adjans); return 1; }

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

supertrees.cpp: In function 'bool checkallequal(std::vector<int>)':
supertrees.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<vec.size();i++)
      |              ~^~~~~~~~~~~
supertrees.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j=i+1;j<vec.size();j++){
      |                 ~^~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j=0;j<vec.size();j++)
      |               ~^~~~~~~~~~~
supertrees.cpp:75:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |    for(int k=0;k<vec.size();k++)
      |                ~^~~~~~~~~~~
supertrees.cpp:95:38: warning: self-comparison always evaluates to true [-Wtautological-compare]
   95 |  if((mx==2&&mn==0&&st.size()==2)||(mx==mx&&mx==2)||(!mx)){
      |                                    ~~^~~~
supertrees.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int j=0;j<vec.size();j++)
      |               ~^~~~~~~~~~~
supertrees.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |    for(int k=j+1;k<vec.size();k++){
      |                  ~^~~~~~~~~~~
supertrees.cpp:132:15: warning: unused variable 'q' [-Wunused-variable]
  132 |   dfs(i);bool q = 1;
      |               ^
supertrees.cpp:129:7: warning: unused variable 'ans' [-Wunused-variable]
  129 |  bool ans = 1;
      |       ^~~
#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...