Submission #1079265

#TimeUsernameProblemLanguageResultExecution timeMemory
1079265Jawad_Akbar_JJConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
180 ms28004 KiB
#include <iostream> #include <vector> #include "supertrees.h" using namespace std; const int NN = 1005; vector<int> nei[NN]; int seen[NN], dfsd[NN]; int d[NN][NN], lab[NN]; void dfs(int u, int r){ dfsd[u] = 1; d[r][u]++; for (int i : nei[u]) if (!dfsd[i]) dfs(i, r); dfsd[u] = 0; } int construct(vector<vector<int>> p){ int n = p.size(); vector<vector<int>> ans(n, vector<int> (n, 0)), comp, comp2; vector<int> out; int z = 0, o = 0, t = 0, th = 0; for (int i=0;i<n;i++) for (int j=0;j<n;j++){ z += p[i][j] == 0; o += p[i][j] == 1; t += p[i][j] == 2; th += p[i][j] == 3; } if (o and z + t + th == 0){ for (int i=1;i<n;i++) ans[i-1][i] = ans[i][i-1] = 1; build(ans); return 1; } if (t + th == 0){ for (int i=0;i<n;i++){ int mx = 0, ind = -1; for (int k=0;k<comp.size();k++){ int cnt = 0; for (int j : comp[k]) cnt += p[i][j]; if (cnt == 0) continue; if (mx > 0 or cnt != comp[k].size()) return 0; ind = k; mx = cnt; } if (ind == -1) comp.push_back({i}); else comp[ind].push_back(i); } for (auto v : comp) for (int j=1;j<v.size();j++) ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1; build(ans); return 1; } if (o == n and th == 0){ for (int i=0;i<n;i++){ int mx = 0, ind = -1; for (int k=0;k<comp.size();k++){ int cnt = 0; for (int j : comp[k]) cnt += p[i][j] == 2; if (cnt == 0) continue; if (mx > 0 or cnt != comp[k].size()) return 0; ind = k; mx = cnt; } if (ind == -1) comp.push_back({i}); else comp[ind].push_back(i); } for (auto v : comp){ for (int j=1;j<v.size();j++) ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1; if (v.size() > 1) ans[v.back()][v[0]] = ans[v[0]][v.back()] = 1; if (v.size() == 2) return 0; } build(ans); return 1; } if (th) return 0; for (int i=0;i<n;i++){ lab[i] = i; int mx = 0, ind = -1; for (int k=0;k<comp.size();k++){ int cnt = 0; for (int j : comp[k]) cnt += p[i][j] == 1; if (cnt == 0) continue; if (cnt == comp[k].size()) ind = k; } if (ind == -1) comp.push_back({i}); else comp[ind].push_back(i); } for (auto v : comp) for (int j=1;j<v.size();j++) ans[v[j]][v[j-1]] = ans[v[j-1]][v[j]] = 1, lab[v[j]] = v[0]; comp.clear(); for (int i=0;i<n;i++){ if (seen[lab[i]]) continue; int ind = -1; for (int k=0;k<comp.size();k++){ int cnt = 0; for (int j : comp[k]) cnt += p[i][j] == 2; if (cnt == 0) continue; if (cnt == comp[k].size()) ind = k; } seen[lab[i]] = 1; if (ind == -1) comp.push_back({i}); else comp[ind].push_back(i); } for (auto v : comp){ if (v.size() == 2) return 0; for (int i=1;i<v.size();i++) ans[v[i]][v[i-1]] = ans[v[i-1]][v[i]] = 1; ans[v[0]][v.back()] = ans[v.back()][v[0]] = 1; } for (int i=0;i<n;i++) for (int j=0;j<n;j++){ if (i == j) ans[i][j] = 0; if (ans[i][j]) nei[i].push_back(j); } for (int i=0;i<n;i++) dfs(i, i); for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (d[i][j] != p[i][j]) return 0; build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for (int k=0;k<comp.size();k++){
      |                 ~^~~~~~~~~~~~
supertrees.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if (mx > 0 or cnt != comp[k].size())
      |                   ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for (int j=1;j<v.size();j++)
      |                 ~^~~~~~~~~
supertrees.cpp:73:18: 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 k=0;k<comp.size();k++){
      |                 ~^~~~~~~~~~~~
supertrees.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     if (mx > 0 or cnt != comp[k].size())
      |                   ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    for (int j=1;j<v.size();j++)
      |                 ~^~~~~~~~~
supertrees.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for (int k=0;k<comp.size();k++){
      |                ~^~~~~~~~~~~~
supertrees.cpp:113:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |    if (cnt == comp[k].size())
      |        ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:106:7: warning: unused variable 'mx' [-Wunused-variable]
  106 |   int mx = 0, ind = -1;
      |       ^~
supertrees.cpp:122:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int j=1;j<v.size();j++)
      |                ~^~~~~~~~~
supertrees.cpp:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for (int k=0;k<comp.size();k++){
      |                ~^~~~~~~~~~~~
supertrees.cpp:137:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |    if (cnt == comp[k].size())
      |        ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:150:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |   for (int i=1;i<v.size();i++)
      |                ~^~~~~~~~~
#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...