Submission #1199092

#TimeUsernameProblemLanguageResultExecution timeMemory
1199092AMel0nConnecting Supertrees (IOI20_supertrees)C++20
100 / 100
120 ms22220 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,N) for(ll i = 0; i < N; i++) #define all(x) (x).begin(), (x).end() #define F first #define S second #include "supertrees.h" vector<int> par; int find(int n) { if (n == par[n]) return par[n]; return par[n] = find(par[n]); } void merge(int a, int b) { a = find(a); b = find(b); if (a == b) return ; par[b] = a; } int construct(vector<vector<int>> path) { int N = path.size(); par.resize(N); iota(all(par), 0); FOR(i, N) { for (int j = i + 1; j < N; j++) { if (path[i][j] == 3) return 0; // bruh if (path[i][j] > 0) merge(i, j); } } FOR(i, N) { for (int j = i + 1; j < N; j++) { if (path[i][j] == 0 && find(i) == find(j)) return 0; } } vector<vector<int>> conn(N); FOR(i, N) conn[find(i)].push_back(i); iota(all(par), 0); FOR(i, N) { for (int j = i + 1; j < N; j++) { if (path[i][j] == 1) merge(i, j); } } FOR(i, N) { for (int j = i + 1; j < N; j++) { if (path[i][j] == 2 && find(i) == find(j)) return 0; } } vector<vector<int>> res(N, vector<int>(N)); FOR(i, N) { if (i != find(i)) { res[i][find(i)] = 1; res[find(i)][i] = 1; } // if i is also in a path 2 component vector<int> c2; for (auto c: conn[i]) { if (c == find(c)) { c2.push_back(c); } } if (c2.size() == 0) continue; if (c2.size() == 1) continue; // either the parent of a path 1 component or only connected to a path 2 (uninitialised) if (c2.size() == 2) return 0; // can't have 2 paths between 2 elements in a component for (int j = 0; j < c2.size(); j++) { res[c2[j]][c2[(j+1)%c2.size()]] = 1; res[c2[(j+1)%c2.size()]][c2[j]] = 1; } } build(res); return 1; } // signed main() { // cin.tie(0); ios::sync_with_stdio(false); // }
#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...