Submission #1242091

#TimeUsernameProblemLanguageResultExecution timeMemory
1242091trimkusConnecting Supertrees (IOI20_supertrees)C++20
100 / 100
124 ms22208 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; 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) { for (int j = 0; j < n; ++j) { if (p[i][j] == 3) return 0; } } for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } vector<bool> vis(n); vector<int> lidx(n), cidx(n); for (int it = 0; it < n; ++it) { if (vis[it]) continue; queue<int> comp; vector<int> cycle; comp.push(it); while (comp.size()) { int x = comp.front(); comp.pop(); if (vis[x]) continue; vector<int> curr_line; cycle.push_back(x); queue<int> qline; qline.push(x); while (qline.size()) { int y = qline.front(); qline.pop(); if (vis[y]) continue; vis[y] = 1; curr_line.push_back(y); cidx[y] = it; lidx[y] = x; for (int j = 0; j < n; ++j) { if (p[y][j] == 2) { comp.push(j); } else if (p[y][j] == 1) { qline.push(j); } } } if (curr_line.size() > 1) { int a = curr_line[0]; for (int i = 1; i < (int)curr_line.size(); ++i) { int b = curr_line[i]; answer[a][b] = answer[b][a] = 1; } } } if (cycle.size() == 2) return 0; if (cycle.size() == 1) continue; for (int i = 0; i < (int)cycle.size(); ++i) { int a = cycle[i]; int b = cycle[(i + 1) % cycle.size()]; answer[a][b] = answer[b][a] = 1; } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (lidx[i] == lidx[j]) { if (p[i][j] != 1) return 0; } else if (cidx[i] == cidx[j]) { if (p[i][j] != 2) return 0; } else { if (p[i][j] != 0) return 0; } } } build(answer); return 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...