| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1245369 | qwusha | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
//#include "supertrees.h"
#include <iostream>
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int inf = 1e9 + 7;
void build(vector<vector<int>> b) {
cout << "possible " << endl;
int n = b.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (b[i][j] == 1) {
cout << i << ' ' << j << endl;
}
}
}
}
struct dsu {
vector<int> par;
vector<int> sz;
void init(int n) {
par.assign(n, 0);
sz.assign(n, 1);
for (int i = 0; i < n; i++) {
par[i] = i;
}
}
int get_par(int v) {
if (par[v] == v) {
return v;
}
int ans = get_par(par[v]);
par[v] = ans;
return ans;
}
void unitik(int v, int u) {
v = get_par(v);
u = get_par(u);
if (sz[v] < sz[u]) {
swap(v, u);
}
sz[v] += sz[u];
par[u] = v;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
dsu dsubig;
dsubig.init(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] > 0 && dsubig.get_par(i) != dsubig.get_par(j)) {
dsubig.unitik(i, j);
}
}
}
bool ok = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i][j] == 0 && dsubig.get_par(i) == dsubig.get_par(j)) {
ok = 0;
}
}
}
if (!ok) {
return 0;
}
vector<vector<int>> b(n, vector<int>(n));
vector<vector<int>> gr(n);
for (int i = 0; i < n; i++) {
gr[dsubig.get_par(i)].push_back(i);
}
dsu grdsu;
map<int, vector<int>> mp;
for (int j = 0; j < n; j++) {
if (gr[j].size() < 2)
continue;
grdsu.init(gr[j].size());
mp.clear();
for (int i = 0; i < gr[j].size(); i++) {
for (int q = i + 1; q < gr[j].size(); q++) {
if (p[gr[j][i]][gr[j][q]] == 1 && grdsu.get_par(i) != grdsu.get_par(q)) {
grdsu.unitik(i, q);
}
}
}
bool ch = 1;
for (int i = 0; i < gr[j].size(); i++) {
for (int q = i + 1; q < gr[j].size(); q++) {
if (p[gr[j][i]][gr[j][q]] >= 2 && grdsu.get_par(i) == grdsu.get_par(q)) {
ch = 0;
}
}
}
if (!ch)
return 0;
for (int i = 0; i < gr[j].size(); i++) {
mp[grdsu.get_par(i)].push_back(i);
}
vector<int> bosses;
for (auto [boss, ve] : mp) {
bosses.push_back(boss);
for (int i = 0; i < ve.size() - 1; i++) {
b[gr[j][ve[i]]][gr[j][ve[i + 1]]] = 1;
b[gr[j][ve[i + 1]]][gr[j][ve[i]]] = 1;
}
}
if (bosses.size() == 1) {
continue;
}
if (bosses.size() == 2) {
return 0;
}
for (int i = 0; i < bosses.size(); i++) {
b[gr[j][bosses[i]]][gr[j][bosses[(i + 1) % bosses.size()]]] = 1;
b[gr[j][bosses[(i + 1) % bosses.size()]]][gr[j][bosses[i]]] = 1;
}
vector<vector<int>> grogra(gr[j].size(), vector<int>(gr[j].size(), -1));
set<pair<int, int>> sus;
for (int i = 0; i < gr[j].size(); i++) {
for (int q = 0; q < gr[j].size(); q++) {
int bi = grdsu.get_par(i), bj = dsubig.get_par(q);
if (grogra[bi][bj] != -1 && grogra[bi][bj] != p[gr[j][i]][gr[j][q]]) {
return 0;
}
grogra[bi][bj] = p[gr[j][i]][gr[j][q]];
if (p[gr[j][i]][gr[j][q]] == 3) {
sus.insert({min(bi, bj), max(bi,bj)});
}
}
}
if (sus.size() > 1) {
return 0;
}
if (sus.size() == 0) {
continue;
}
if (bosses.size() == 3) {
return 0;
}
b[gr[j][bosses[sus[0].fi]]][gr[j][bosses[sus[0].se]]] = 1;
b[gr[j][bosses[sus[0].se]]][gr[j][bosses[sus[0].fi]]] = 1;
}
build(b);
return 1;
}
int main() {
int n;
cin >> n;
vector<vector<int>> w(n, vector<int> (n, 2));
int va = construct(w);
}