Submission #591180

#TimeUsernameProblemLanguageResultExecution timeMemory
591180SirCovidThe19thConnecting Supertrees (IOI20_supertrees)C++17
46 / 100
229 ms22356 KiB
#include <bits/stdc++.h> #include "supertrees.h" using namespace std; #define FOR(i, x, y) for (int i = x; i < y; i++) int construct(vector<vector<int>> p){ int n = p.size(); FOR(i, 0, n) FOR(j, 0, n) if (p[i][j] == 3) return 0; vector<vector<int>> ans(n, vector<int>(n, 0)); bool vis[n] = {}; int par[n]; iota(par, par + n, 0); function<int(int)> get = [&](int i){ return i == par[i] ? i : par[i] = get(par[i]); }; auto merge = [&](int a, int b){ par[get(a)] = get(b); }; FOR(src, 0, n) if (!vis[src]){ vector<int> cmp; FOR(i, 0, n) if (p[src][i]){ cmp.push_back(i); if (vis[i]) return 0; vis[i] = 1; } for (int i : cmp) for (int j : cmp) if (p[i][j] == 1) merge(i, j); for (int i : cmp) for (int j : cmp) if (!(p[i][j] and ((get(i) == get(j) and p[i][j] == 1) or (get(i) != get(j) and p[i][j] == 2)))) return 0; bool use[n] = {}; vector<int> head; for (int i : cmp){ int c = get(i); if (!use[c]) head.push_back(c), use[c] = 1; if (i != c) ans[i][c] = ans[c][i] = 1; } FOR(i, 0, head.size()){ int a = head[i]; int b = head[(i + 1) % head.size()]; if (a != b) ans[a][b] = ans[b][a] = 1; } } build(ans); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, x, y) for (int i = x; i < y; i++)
......
   41 |         FOR(i, 0, head.size()){
      |             ~~~~~~~~~~~~~~~~~           
supertrees.cpp:41:9: note: in expansion of macro 'FOR'
   41 |         FOR(i, 0, head.size()){
      |         ^~~
#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...