| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1264000 | Noname_1900 | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 1000;
int boss[NMAX];
vector<int> dansComp[NMAX];
vector<int> chemins[3][NMAX];
int findBoss(int noeud)
{
if(boss[noeud] == noeud) return noeud;
return boss[noeud] = findBoss(boss[noeud]);
}
int size[NMAX];
bool merge(int a, int b)
{
a = findBoss(a);
b = findBoss(b);
if(a == b) return false;
if(size[b] > size[a])
{
swap(a, b);
}
size[a] += size[b];
boss[b] = a;
for(int i : dansComp[b]) dansComp[a].push_back(i);
return true;
}
vector<vector<int>> answer;
void creer(int a, int b)
{
answer[a][b] = 1;
answer[b][a] = 1;
merge(a, b);
}
bool dansCycle[NMAX];
void parcours(int noeud)
{
for(int pro : chemins[1][noeud])
{
if(findBoss(pro) == findBoss(noeud)) continue;
creer(noeud, pro);
parcours(pro);
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
answer.resize(n, vector<int>(n));
for(int i = 0; i < n; i++)
{
size[i] = 1;
boss[i] = i;
dansComp[i].push_back(i);
for(int v = 0; v < n; v++) answer[i][v] = 0;
}
for(int i = 0; i < n; i++)
{
for(int c = 0; c < n ; c ++)
{
int type = p[i][c];
chemins[type][i].push_back(c);
}
}
/*
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < i; autre++)
{
if(p[i][autre] == 1)
{
creer(findBoss(i), findBoss(autre));
}
}
}
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < i; autre++)
{
if(p[i][autre] == 0)
{
if(findBoss(i) == findBoss(autre)) return 0;
}
}
}
/** */
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
if(p[i][autre] == 2)
{
merge(findBoss(i), findBoss(autre));
}
}
}
// cout << "passe" << endl;
/**
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
//cout << i << " " << autre << endl;
if(i == autre) continue;
if(p[i][autre] == 0)
{
if(findBoss(i) == findBoss(autre)) return 0;
}
}
}
//cout << "passe" << endl;
/** */
// cycle de 2
for(int i = 0; i < n; i++)
{
if(findBoss(i) == i)
{
if(dansComp[i].size() == 1) continue;
//if(dansComp[i].size() == 2) return 0;
// cout << endl;
for(int iDansComp=0; iDansComp < dansComp[i].size(); iDansComp++)
{
//cout << dansComp[i][iDansComp] << " ";
int b;
if(iDansComp == 0)
{
b = dansComp[i][dansComp[i].size()-1];
}
else
b = dansComp[i][iDansComp-1];
int a = dansComp[i][iDansComp];
dansCycle[a] = true;
creer(a, b);
}
}
}
// parcours pour arbre depuis cycle
for(int i = 0; i < n; i++)
{
if(!dansCycle[i]) continue;
parcours(i);
}
//reste
for(int i = 0; i < n; i++) parcours(i);
for(int i = 0; i < n; i++)
{
for(int autre = 0; autre < n; autre++)
{
if(((p[i][autre] == 0) && (findBoss(i) == findBoss(autre))) || ((p[i][autre] > 0) && (findBoss(i) != findBoss(autre)))) return 0;
}
}
build(answer);
return 1;
}