Submission #786977

#TimeUsernameProblemLanguageResultExecution timeMemory
786977acatmeowmeowConnecting Supertrees (IOI20_supertrees)C++14
21 / 100
167 ms24268 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N = 1e3; int par[N + 5], sz[N + 5]; vector<int> ls[N + 5]; int vertex[N + 5]; bool vis[N + 5]; int find(int x) { return x == par[x] ? x : find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } void unite(int x, int y) { x = find(x), y = find(y); if (sz[x] < sz[y]) swap(x, y); sz[x] += sz[y], par[y] = x; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); // check connectivity for (int i = 0; i < n; i++) par[i] = i, sz[i] = 1; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (p[i][j] && !same(i, j)) unite(i, j); } } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (!p[i][j] && same(i, j)) return 0; } } for (int i = 0; i < n; i++) ls[find(i)].push_back(i); for (int i = 0; i < n; i++) vertex[i] = -1; vector<vector<int>> b(n, vector<int>(n)); for (auto&arr : ls) { if (arr.empty()) continue; int sz = arr.size(), hasTwo = false, hasThree = false; for (int i = 0; i < sz; i++){ for (int j = i + 1; j < sz; j++) { int u = arr[i], v = arr[j]; hasTwo |= p[u][v] == 2, hasThree |= p[u][v] == 3; } } if (hasTwo && hasThree) return 0; if (!hasTwo && !hasThree) { for (int i = 0; i + 1 < sz; i++){ int u = arr[i], v = arr[i + 1]; b[u][v] = b[v][u] = 1; } continue; } vector<int> loop; for (int i = 0, flag = 0; !flag && i < sz; i++) { for (int j = i + 1; j < sz; j++) { int u = arr[i], v = arr[j]; if (p[u][v] >= 2) { loop.push_back(u), loop.push_back(v); vertex[u] = -1, vertex[v] = -1; flag = true; break; } } } for (int i = 0; i < sz; i++) { int valid = 1, u = arr[i]; for (auto&v : loop) valid &= u != v && p[u][v] >= 2; if (valid) loop.push_back(i); } if (hasTwo && loop.size() <= 2) return 0; else if (hasThree && loop.size() <= 3) return 0; for (int i = 0; i < loop.size(); i++) { int u = loop[i], v = loop[(i + 1) % loop.size()]; b[u][v] = b[v][u] = 1; } if (hasThree) b[loop[0]][loop[2]] = b[loop[2]][loop[0]] = 1; queue<int> q; for (auto&v : loop) q.push(v), vis[v] = true; while (q.size()) { int u = q.front(); q.pop(); for (int i = 0; i < sz; i++) { int v = arr[i]; if (v == u || vis[v] || p[v][u] != 1) continue; vis[v] = true; if (vertex[u] == -1) vertex[v] = u; else vertex[v] = vertex[u]; q.push(v); b[u][v] = b[v][u] = 1; } } for (int i = 0; i + 1 < sz; i++) { int u = arr[i], v = arr[i + 1]; if (p[u][v] > 1 && vertex[u] != -1 && vertex[v] != -1 && vertex[u] != vertex[v]) return 0; } } build(b); return 1; } /*static int n; static std::vector<std::vector<int>> p; static std::vector<std::vector<int>> b; static bool called = false; static void check(bool cond, std::string message) { if (!cond) { printf("%s\n", message.c_str()); fclose(stdout); exit(0); } } void build(std::vector<std::vector<int>> _b) { check(!called, "build is called more than once"); called = true; check((int)_b.size() == n, "Invalid number of rows in b"); for (int i = 0; i < n; i++) { check((int)_b[i].size() == n, "Invalid number of columns in b"); } b = _b; } int main() { //assert(scanf("%d", &n) == 1); cin >> n; p.resize(n); for (int i = 0; i < n; i++) { p[i].resize(n); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { //assert(scanf("%d", &p[i][j]) == 1); cin >> p[i][j]; } } //fclose(stdin); int possible = construct(p); check(possible == 0 || possible == 1, "Invalid return value of construct"); if (possible == 1) { check(called, "construct returned 1 without calling build"); } else { check(!called, "construct called build but returned 0"); } printf("%d\n", possible); if (possible == 1) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j) { printf(" "); } printf("%d", b[i][j]); } printf("\n"); } } // fclose(stdout); }*/

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < loop.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...