| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1069911 | 2024-08-22T09:58:37 Z | hasan2006 | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KB |
//#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 2e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N];
//int press(string a){}
int construct(vector<vector<int>> v){
ll i , j , l , r , s = 0, f , n , m , x , y , k;
n = v.size();
vector<vector<int>>c(n);
for(i = 0; i < n; i++)
c[i].resize(n);
for(i = 0; i < n; i++){
if(b[i] != 0)
continue;
vector<pair<int,pair<int,int>>>vc;
vector<int>v1 , v2 , v3;
for(j = 0; j < n; j++)
if(v[i][j] != 0){
b[j] = 1 , v1.pb(j);
}
l = r = 0;
for(x = 0; x < v1.size(); x++){
if(b[v1[x]] == 2)
continue;
b[v1[x]] = 3;
f = v1[x];
for(y = x + 1; y < v1.size(); y++){
vc.pb({v[v1[x]][v1[y]] , {v1[x] , v1[y]}});
if(v[v1[x]][v1[y]] == 2)
l = 1;
else if(v[v1[x]][v1[y]] == 3)
r = 1;
else{
if(b[v1[y]] == 2)
return 0;
c[v1[y]][f] = c[f][v1[y]] = 1;
b[v1[y]] = 2;
f = v1[y];
}
}
}
sort(all(vc));
if(v1.size() == 1)
continue;
if((l == 1 && r == 1) || vc.front().fi == 0)
return 0;
set<int>st;
for(auto to : v1){
st.insert(to);
if(b[to] == 3)
v2.pb(to);
else
v3.pb(to);
}
if(v2.size()){
if(v2.size() <= vc.back().fi){
return 0;
}
f = v2.back();
for(auto to : v2)
c[f][to] = c[to][f] = 1 , f = to;
if(vc.back().fi == 3)
c[v2[0]][v2[2]] = c[v2[2]][v2[0]] = 1;
}
for(auto to : v1){
ll L = 0 ,R = 0 , s =0;
for(j = 0; j < n ; j++)
if(v[to][j] != 0){
if(st.find(j) == st.end())
return 0;
s++;
if(to == j)
continue;
if(v[to][j] == 2)
L = 1;
else if(v[to][j] == 3)
R = 1;
else {
if(b[to] == 1 || b[j] == 1)
return 0;
}
}
if((L > l) || (R > r) || s != v1.size())
return 0;
}
}
// for(i = 0; i < n; i++){
// for(j = 0; j < n; j++)
// cout<<c[i][j]<<" ";
// cout<<"\n";
// }
build(c);
return 1;
}
/*
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout<<construct({{1, 1, 2, 2}, {1, 1, 2, 2}, {2, 2, 1, 2}, {2, 2, 2, 1}});
}*/
// Author : حسن