Submission #625305

#TimeUsernameProblemLanguageResultExecution timeMemory
625305TrunktyConnecting Supertrees (IOI20_supertrees)C++14
100 / 100
224 ms22156 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); } if(p[i][j]==3){ return 0; } } } 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; }

Compilation message (stderr)

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