제출 #362543

#제출 시각아이디문제언어결과실행 시간메모리
362543valerikk슈퍼트리 잇기 (IOI20_supertrees)C++17
100 / 100
275 ms27504 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N = 1007; vector<int> g[N]; bool vis[N]; int cmp[N]; vector<int> comp; int par[N]; int find_par(int v) { return par[v] == v ? v : par[v] = find_par(par[v]); } bool unite(int v, int u) { v = find_par(v); u = find_par(u); par[v] = u; return v != u; } void dfs(int v, int st) { vis[v] = true; cmp[v] = st; comp.push_back(v); for (int u : g[v]) { if (!vis[u]) dfs(u, st); } } int construct(vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; i++) g[i].clear(); for (int i = 0; i < n; i++) { if (p[i][i] != 1) return 0; for (int j = 0; j < i; j++) { if (p[i][j] != p[j][i]) return 0; if (p[i][j] == 3) return 0; if (p[i][j] > 0) { g[i].push_back(j); g[j].push_back(i); } } } vector<vector<int>> b(n, vector<int>(n, 0)); auto add_edge = [&](int v, int u) { b[v][u] = b[u][v] = 1; }; for (int i = 0; i < n; i++) { vis[i] = false; cmp[i] = -1; } for (int st = 0; st < n; st++) { if (!vis[st]) { comp = {}; dfs(st, st); bool ok = true; for (int v : comp) { for (int u : comp) ok &= p[v][u] > 0; for (int i = 0; i < n; i++) { if (cmp[i] != st) ok &= p[v][i] == 0; } } if (!ok) return 0; bool has = false; for (int v : comp) { for (int u : comp) has |= p[v][u] == 2; } if (has) { for (int i = 0; i < n; i++) par[i] = i; for (int v : comp) { for (int u : comp) { if (p[v][u] == 1) unite(v, u); } } for (int v : comp) { for (int u : comp) { if (find_par(v) == find_par(u) && p[v][u] == 2) return 0; if (find_par(v) != find_par(u) && p[v][u] == 1) return 0; } } for (int v : comp) find_par(v); vector<int> arr; for (int v : comp) arr.push_back(find_par(v)); sort(arr.begin(), arr.end()); arr.erase(unique(arr.begin(), arr.end()), arr.end()); if (arr.size() < 3) return 0; vector<vector<int>> arrs(arr.size()); for (int v : comp) { arrs[lower_bound(arr.begin(), arr.end(), find_par(v)) - arr.begin()].push_back(v); } for (int i = 0; i < arr.size(); i++) { for (int j = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]); } for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]); } else { for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]); } } } build(b); return 1; }

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:95:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 for (int i = 0; i < arr.size(); i++) {
      |                                 ~~^~~~~~~~~~~~
supertrees.cpp:96:43: 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 = 0; j + 1 < arrs[i].size(); j++) add_edge(arrs[i][j], arrs[i][j + 1]);
      |                                     ~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp:98:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 for (int i = 0; i < arr.size(); i++) add_edge(arr[i], arr[(i + 1) % (int)arr.size()]);
      |                                 ~~^~~~~~~~~~~~
supertrees.cpp:100:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 for (int i = 0; i + 1 < comp.size(); i++) add_edge(comp[i], comp[i + 1]);
      |                                 ~~~~~~^~~~~~~~~~~~~
#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...