| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 321423 | grt | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;
#define ST first
#define ND second
#define PB push_back
const int nax = 1000 + 10;
int n;
vi Graph[nax];
bool visited[nax];
vector<vi>comp;
vector<vi>access;
vi cur;
void build(vector<vi>v);
void dfs(int x) {
visited[x] = 1;
cur.PB(x);
for(int nbh : Graph[x]) {
if(!visited[nbh]) dfs(nbh);
}
}
int construct(vector<vi> p) {
int cnt3 = 0;
n = (int)p.size();
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(p[i - 1][j - 1] == 1) {
Graph[i].PB(j);
}
if(p[i - 1][j - 1] == 3) cnt3++;
}
}
if(cnt3 > 0) return 0;
bool ok = 1;
for(int i = 1; i <= n; ++i) {
if(!visited[i]) {
cur = {};
dfs(i);
comp.PB(cur);
for(int x : cur) {
for(int y : cur) {
if(p[x - 1][y - 1] != 1) ok = 0;
}
}
}
}
if(!ok) return 0;
for(auto c : comp) {
cur = {};
int id = 0;
for(auto c2 : comp) {
if(c2 == c) {
cur.PB(id);
id++;
continue;
}
int cnt0 = 0, cnt1 = 0, cnt2 = 0;
for(int x : c) {
for(int y : c2) {
if(p[x - 1][y - 1] == 0) cnt0++;
else if(p[x - 1][y - 1] == 1) cnt1++;
else if(p[x - 1][y - 1] == 2) cnt2++;
}
}
assert(cnt1 == 0);
if(cnt0 > 0 && cnt2 > 0) ok = 0;
if(cnt2 > 0) {
cur.PB(id);
}
id++;
}
access.PB(cur);
if((int)cur.size() == 2) ok = 0;
}
if(!ok) return 0;
for(int i = 0; i <= n; ++i) visited[i] = 0;
for(int i = 0; i < (int)comp.size(); ++i) {
if(!visited[i]) {
cur = access[i];
visited[i] = 1;
for(int x : cur) {
visited[x] = 1;
if(cur != access[x]) ok = 0;
}
}
}
if(!ok) return 0;
vector<vi>g(n);
for(int i = 0; i < n; ++i) g[i].resize(n);
for(int nr = 0; nr < (int)access.size(); ++nr) {
for(int i = 0; i < (int)comp[nr].size() - 1; ++i) {
g[comp[nr][i] - 1][comp[nr][i + 1] - 1] = g[comp[nr][i + 1] - 1][comp[nr][i] - 1] = 1;
}
//cout << nr << " ";
for(int i = 0; i < (int)access[nr].size(); ++i) {
if(access[nr][i] == nr) {
int pr = i - 1;
if(pr < 0) pr = (int)acces[nr].size() - 1;
g[comp[access[pr]][0] - 1][comp[nr][0] - 1] = g[comp[nr][0] - 1][comp[access[pr]][0] - 1] = 1;
}
}
}
build(g);
//for(int i = 0; i < n; ++i) {
// for(int j = 0; j < n; ++j) {
// cout << g[i][j] << " ";
// }
// cout << "\n";
//}
return 1;
}
//int main() {
//cout << construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
//cout << construct({{1,3},{3,1}});
//}