제출 #625304

#제출 시각아이디문제언어결과실행 시간메모리
625304Trunkty슈퍼트리 잇기 (IOI20_supertrees)C++14
96 / 100
216 ms22216 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; typedef long long ll; //#define int ll #include "supertrees.h" int root[1005]; vector<int> ans[1005]; int rootp[1005]; vector<int> part[1005]; int findroot(int x){ if(root[x]!=x){ root[x] = findroot(root[x]); } return root[x]; } void domerge(int a, int b){ a = findroot(a); b = findroot(b); root[a] = b; } int findrootp(int x){ if(rootp[x]!=x){ rootp[x] = findrootp(rootp[x]); } return rootp[x]; } void domergep(int a, int b){ a = findrootp(a); b = findrootp(b); rootp[a] = b; } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ret; for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); ret.push_back(row); } for(int i=0;i<n;i++){ root[i] = i; rootp[i] = i; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]){ domerge(i,j); } if(p[i][j]==1){ domergep(i,j); } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(p[i][j]==0 and findroot(i)==findroot(j)){ return 0; } if(p[i][j]==2 and findrootp(i)==findrootp(j)){ return 0; } } } for(int i=0;i<n;i++){ ans[findroot(i)].push_back(i); part[findrootp(i)].push_back(i); } for(int i=0;i<n;i++){ for(int j=1;j<part[i].size();j++){ ret[part[i][j-1]][part[i][j]] = 1; ret[part[i][j]][part[i][j-1]] = 1; } } for(int i=0;i<n;i++){ set<int> s; vector<int> v; for(int j=0;j<ans[i].size();j++){ s.insert(findrootp(ans[i][j])); } for(int j:s){ v.push_back(j); } for(int j=1;j<v.size();j++){ ret[v[j]][v[j-1]] = 1; ret[v[j-1]][v[j]] = 1; } if(v.size()<=1){ continue; } else if(v.size()==2){ return 0; } ret[v[0]][v.back()] = 1; ret[v.back()][v[0]] = 1; } build(ret); return 1; }

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

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int j=1;j<part[i].size();j++){
      |                     ~^~~~~~~~~~~~~~~
supertrees.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j=0;j<ans[i].size();j++){
      |                     ~^~~~~~~~~~~~~~
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 j=1;j<v.size();j++){
      |                     ~^~~~~~~~~
#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...