| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 370000 | iliccmarko | 슈퍼트리 잇기 (IOI20_supertrees) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
int b[N][N];
void build(vector<vector<int> > b)
{
for(int i = 0;i<n;i++)
{
for(int x : g[i])
b[i][x] = 1;
}
}
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++)
{
for(int j = 0;j<n;j++)
{
if(i==j) continue;
if(p[i][j]==3)
{
g[i].pb(j);
grupa[i] = 3;
}
}
}
for(int i = 0;i<n;i++)
{
if(grupa[i]) continue;
for(int j = 0;j<n;j++)
{
if(i==j) continue;
if(grupa[j]) continue;
if(p[i][j]==2)
{
grupa[i] = 2;
g[i].pb(j);
}
}
}
for(int i = 0;i<n;i++)
{
if(grupa[i]) continue;
for(int j = 0;j<n;j++)
{
if(i==j) continue;
if(grupa[j]) continue;
if(p[i][j]==1)
{
grupa[i] = 1;
g[i].pb(j);
}
}
}
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) raz++;
if(p[i][j]==x) cnt++;
}
if(raz) moze = 0;
if(cnt!=s[parent[i]]) moze = 0;
}
if(!moze) return 0;
build(b);
return 1;
}