Submission #1046557

#TimeUsernameProblemLanguageResultExecution timeMemory
1046557sofijavelkovskaConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
127 ms22400 KiB
#include "supertrees.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; int construct(vector<vector<int> > adj) { int n=adj.size(); vector<vector<int> > answer; for (int i=0; i<n; i++) { vector<int> row; row.resize(n, 0); answer.push_back(row); } for (int i=0; i<n; i++) for (int j=i+1; j<n; j++) if (adj[i][j]==3) return 0; int visited[n]={0}; queue<int> q; vector<int> component; vector<vector<int> > subcomponents; for (int i=0; i<n; i++) { if (visited[i]) continue; visited[i]=1; q.push(i); component.clear(); while (!q.empty()) { int x=q.front(); q.pop(); component.push_back(x); for (int j=0; j<n; j++) if (adj[x][j]>0 && !visited[j]) { visited[j]=1; q.push(j); } } subcomponents.clear(); for (auto x : component) { if (visited[x]==2) continue; visited[x]=2; q.push(x); vector<int> newcomp; subcomponents.push_back(newcomp); while (!q.empty()) { int y=q.front(); q.pop(); subcomponents.back().push_back(y); for (auto z : component) if (y!=z && adj[y][z]==1 && visited[z]!=2) { visited[z]=2; q.push(z); } } } for (int j=0; j<subcomponents.size(); j++) { for (int t=0; t<subcomponents[j].size(); t++) for (int k=t+1; k<subcomponents[j].size(); k++) if (adj[subcomponents[j][t]][subcomponents[j][k]]!=1) return 0; for (auto x : subcomponents[j]) for (int t=0; t<subcomponents.size(); t++) { if (t==j) continue; for (auto y : subcomponents[t]) if (adj[x][y]!=2) return 0; } } if (subcomponents.size()==2) { for (int j=0; j<component.size(); j++) for (int t=j+1; t<component.size(); t++) if (adj[j][t]!=1) return 0; } for (int j=0; j<subcomponents.size(); j++) for (int t=0; t<subcomponents[j].size()-1; t++) { int x=subcomponents[j][t]; int y=subcomponents[j][t+1]; answer[x][y]=1; answer[y][x]=1; } if (subcomponents.size()==1) continue; if (subcomponents.size()==2) { int x=subcomponents[0][0]; int y=subcomponents[1][0]; answer[x][y]=1; answer[y][x]=1; } for (int j=0; j<subcomponents.size(); j++) { int x=subcomponents[j][0]; int y=subcomponents[(j+1)%subcomponents.size()][0]; answer[x][y]=1; answer[y][x]=1; } } build(answer); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:17:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   17 |     for (int i=0; i<n; i++)
      |     ^~~
supertrees.cpp:21:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   21 |  int visited[n]={0};
      |  ^~~
supertrees.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int j=0; j<subcomponents.size(); j++)
      |                       ~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:68:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for (int t=0; t<subcomponents[j].size(); t++)
      |                           ~^~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:69:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 for (int k=t+1; k<subcomponents[j].size(); k++)
      |                                 ~^~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:73:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |                 for (int t=0; t<subcomponents.size(); t++)
      |                               ~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for (int j=0; j<component.size(); j++)
      |                           ~^~~~~~~~~~~~~~~~~
supertrees.cpp:85:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for (int t=j+1; t<component.size(); t++)
      |                                 ~^~~~~~~~~~~~~~~~~
supertrees.cpp:89:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int j=0; j<subcomponents.size(); j++)
      |                       ~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for (int t=0; t<subcomponents[j].size()-1; t++)
      |                           ~^~~~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:106:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int j=0; j<subcomponents.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...