Submission #301525

#TimeUsernameProblemLanguageResultExecution timeMemory
301525kevinsogoConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
282 ms26360 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; vector<int> get_comp(const vector<vector<int>>& adj, vector<bool>& vis, int s) { assert(!vis[s]); vis[s] = true; vector<int> que(1, s); for (int f = 0; f < que.size(); f++) { int i = que[f]; assert(vis[i]); for (int j : adj[i]) { if (!vis[j]) { vis[j] = true; que.push_back(j); } } } return que; } int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> ans(n, vector<int>(n)); vector<vector<int>> adjtree(n), adjcycl(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 3) return 0; if (p[i][j] == 1) adjtree[i].push_back(j); } } vector<vector<int>> trees; vector<int> roots; vector<bool> vis(n); for (int s = 0; s < n; s++) { if (!vis[s]) { trees.push_back(get_comp(adjtree, vis, s)); roots.push_back(trees.back().back()); } } for (int t1 = 0; t1 < trees.size(); t1++) { for (int t2 = 0; t2 < trees.size(); t2++) { int target = p[roots[t1]][roots[t2]]; if (target == 0 && t1 == t2) return 0; if (target == 1 && t1 != t2) return 0; if (target == 2 && t1 == t2) return 0; for (int i1 : trees[t1]) for (int i2 : trees[t2]) { if (p[i1][i2] != target) return 0; } } } // build trees for (auto& tree : trees) { for (int i = 1; i < tree.size(); i++) { ans[tree[0]][tree[i]] = 1; } } // build cycles for (int i : roots) for (int j : roots) { if (p[i][j] == 2) adjcycl[i].push_back(j); } vis = vector<bool>(n); for (int s : roots) { if (!vis[s]) { vector<int> cycle = get_comp(adjcycl, vis, s); for (int i : cycle) for (int j : cycle) { if (i != j && p[i][j] != 2) return 0; } if (cycle.size() > 1) { for (int i = 0, j = cycle.size() - 1; i < cycle.size(); j = i++) { ans[cycle[i]][cycle[j]] = 1; } } if (cycle.size() == 2) return 0; } } // fix grid for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans[i][j] |= ans[j][i]; ans[j][i] |= ans[i][j]; } } for (int i = 0; i < n; i++) { ans[i][i] = 0; } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'std::vector<int> get_comp(const std::vector<std::vector<int> >&, std::vector<bool>&, int)':
supertrees.cpp:9:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int f = 0; f < que.size(); f++) {
      |                     ~~^~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:44:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int t1 = 0; t1 < trees.size(); t1++) {
      |                      ~~~^~~~~~~~~~~~~~
supertrees.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int t2 = 0; t2 < trees.size(); t2++) {
      |                          ~~~^~~~~~~~~~~~~~
supertrees.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 1; i < tree.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:75:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for (int i = 0, j = cycle.size() - 1; i < cycle.size(); j = 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...