Submission #838665

#TimeUsernameProblemLanguageResultExecution timeMemory
838665SoulKnightConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
174 ms22168 KiB
#include "supertrees.h" #include <vector> #include <iostream> #include <numeric> #include <cstring> using namespace std; #define ll long long #define ln '\n' const int N = 1000 + 5; int par[N], who[N]; vector<int> com[N]; int find(int u){return ((u == par[u])? u: par[u]=find(par[u]));} int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } iota(par, par+n, 0); memset(who, -1, sizeof(who)); for (int i = 0; i < n; i++){ for (int j = i+1; j < n; j++){ if (p[i][j] == 0) continue; if (p[i][j] == 3) return 0; par[find(i)] = find(j); } } for (int i = 0; i < n; i++){ com[find(i)].push_back(i); } for (int i = 0; i < n; i++){ if (com[i].size() <= 1) continue; vector<int> cycle; bool has3 = false, has2 = false; for (auto& v: com[i]){ vector<int> line; line.push_back(v); for (auto& j: com[i]){ if (v == j) continue; if (p[v][j] == 2) {has2 = true; continue;} if (p[v][j] == 3) {has3 = true; continue;} if (p[j][v] == 0) return 0; if (who[j] != who[v]) return 0; if (who[j] == -1) who[j] = v; line.push_back(j); } if (has2 && has3) return 0; if (who[v] == -1) { who[v] = v; cycle.push_back(v); for (int k = 1; k < line.size(); k++) { answer[line[k]][line[k-1]] = answer[line[k-1]][line[k]] = 1; } } } if (cycle.size() == 1) continue; if (cycle.size() == 2) return 0; for (int i = 1; i < cycle.size(); i++){ answer[cycle[i-1]][cycle[i]] = answer[cycle[i]][cycle[i-1]] = 1; } answer[cycle.front()][cycle.back()] = answer[cycle.back()][cycle.front()] = 1; if (has3){ if (cycle.size() == 3) return 0; answer[cycle[0]][cycle[cycle.size()-2]] = 1; answer[cycle[cycle.size()-2]][cycle[0]] = 1; } } build(answer); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int k = 1; k < line.size(); k++) {
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for (int i = 1; i < cycle.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...