| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 370017 | 2021-02-22T21:58:09 Z | iliccmarko | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
const int N = 1050;
vector<int> g[N];
int n;
int s[N], parent[N];
int grupa[N];
void build(std::vector<std::vector<int>> b)
{
}
int find_parent(int u)
{
while(parent[u]!=u)
{
parent[u] = parent[parent[u]];
u = parent[u];
}
return u;
}
void dsu(int u, int v)
{
u = find_parent(u);
v = find_parent(v);
if(u!=v)
{
if(s[u]<s[v]) swap(u, v);
s[u] += s[v];
parent[v] = u;
}
}
int construct(vector<vector<int> > p)
{
n = len(p);
for(int i = 0;i<n;i++) if(p[i][i]!=1) return 0;
for(int i = 0;i<n;i++)
{
for(int j = i+1;j<n;j++)
{
if(p[i][j]==3)
{
grupa[i] = grupa[j] = 3;
g[i].pb(j);
g[j].pb(i);
}
}
}
for(int i = 0;i<n;i++)
{
if(grupa[i]) continue;
for(int j = i+1;j<n;j++)
{
if(i==j) continue;
if(grupa[j]) continue;
if(p[i][j]==2)
{
grupa[i] = 2;
grupa[j] = 2;
g[i].pb(j);
g[j].pb(i);
}
}
}
for(int i = 0;i<n;i++)
{
if(grupa[i]) continue;
for(int j = i+1;j<n;j++)
{
if(i==j) continue;
if(grupa[j]) continue;
if(p[i][j]==1)
{
grupa[i] = grupa[j] = 1;
g[i].pb(j);
g[j].pb(i);
}
}
}
for(int i = 0;i<n;i++)
{
for(int x : g[i])
dsu(i, x);
}
for(int i = 0;i<n;i++) parent[i] = find_parent(i);
int moze = 1;
for(int i = 0;i<n;++i)
{
int x = grupa[i];
int cnt = 0;
int raz = 0;
for(int j = 0;j<n;j++)
{
if(i==j) continue;
if(p[i][j]!=x&&x!=0) raz++;
if(p[i][j]==x) cnt++;
}
if(raz) moze = 0;
if(cnt!=s[parent[i]]&&x!=0) moze = 0;
}
if(!moze) return 0;
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row;
row.resize(n);
answer.push_back(row);
}
for(int i = 0;i<n;i++) for(int j = 0;j<n;j++) answer[i][j] = 0;
for(int i = 0;i<n;i++) for(int x : g[i]) answer[i][x] = 1;
build(answer);
return 1;
}