| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 482707 | PoPularPlusPlus | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}
/*void build(vector<vector<int>>& ans){
for(int i = 0; i < (int)ans.size(); i++){
for(int j = 0; j < (int)ans.size(); j++)cout << ans[i][j] << ' ';
cout << '\n';
}
}*/
struct UFDS {
vector<int> p,siz;
void init(int n){
p.resize(n + 3);
siz.resize(n + 3);
for(int i = 0; i <= n; i++){
p[i] = i;
siz[i] = 1;
}
}
int get(int x){
return p[x]=(x==p[x] ? x : get(p[x]));
}
void unio(int u , int v){
int a = get(u);
int b=get(v);
if(a==b)return;
if(siz[a]>siz[b])swap(a,b);
p[b]=a;
siz[a]+=siz[b];
}
};
vector<vector<int>> b;
vector<int> adj[2003];
int help(vector<int>& v){
UFDS uf;
int n = v.size();
uf.init(n + 2);
for(int i = 0; i < n; i++){
for(int j = i+1; j < n;j++){
if(b[v[i]][v[j]] == 1){
uf.unio(v[i],v[j]);
}
}
}
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(uf.get(v[i]) == uf.get(v[j]) && b[v[i]][v[j]] == 2)return -1;
}
}
vector<vector<int>> v1;
bool vis1[n + 1];
memset(vis1,0,sizeof vis1);
for(int i = 0; i < n; i++){
if(!vis1[v[i]]){
vector<int> x;
x.pb(v[i]);
for(int j = i+1; j < n; j++){
if(uf.get(v[i]) == uf.get(v[j])){
x.pb(v[j]);
vis1[v[j]] = 1;
}
}
v1.pb(x);
}
}
for(int i = 0; i < (int)v1.size(); i++){
if(i == (int)v1.size()-1){
if(i!=0){
adj[v1[i][0]].pb(v1[0][0]);
adj[v1[0][0]].pb(v1[i][0]);
}
}
else {
adj[v1[i][0]].pb(v1[i + 1][0]);
adj[v1[i+1][0]].pb(v1[i][0]);
}
}
for(int i = 0; i < (int)v1.size(); i++){
for(int j = 1; j < (int)v1[i].size(); j++){
adj[v1[i][j]].pb(v1[i][j-1]);
adj[v1[i][j-1]].pb(v1[i][j]);
}
}
return 1;
}
int construct(vector<vector<int>>& v){
int n = v.size();
UFDS d;
b = v;
d.init(n + 2);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(v[i][j]!=0)d.unio(i,j);
}
}
for(int i = 0; i < n; i++){
for(int j =0 ;j < n; j++){
if(v[i][j] == 0 && d.get(i) == d.get(j))return -1;
}
}
vector<vector<int>> com;
bool vis[n + 1];
memset(vis,0,sizeof vis);
for(int i = 0; i < n; i++){
if(!vis[i]){
vector<int> x;
x.pb(i);
for(int j = i+1; j < n; j++){
if(d.get(i) == d.get(j)){
x.pb(j);
vis[j] = 1;
}
}
com.pb(x);
}
}
vector<vector<int>> ans(n,vector<int> (n,0));
for(int i = 0; i < (int)com.size(); i++){
int x = help(com[i]);
if(x == -1)return 0;
}
for(int i = 0; i < n; i++){
for(int j : adj[i]){
ans[i][j] = 1;
}
}
build(ans);
return 1;
}
/*
void solve(){
int n;
cin >> n;
vector<vector<int>> t(n,vector<int>(n));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)cin >> t[i][j];
}
construct(t);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin >> t;while(t--)
solve();
return 0;
}*/