| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1069975 | hasan2006 | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
b[v1[x]] = 3;
f = v1[x];
vector<int>vv;
vv.pb(f);
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[x]] == 3){
if(b[v1[y]] == 2)
return 0;
c[v1[y]][f] = c[f][v1[y]] = 1;
b[v1[y]] = 2;
f = v1[y];
vv.pb(f);
}
}
for(auto to : vv){
s= 0;
for(auto to1:vv)
if(v[to][to1] != 1)
return 0;
for(j = 0; j < n; j++)
if(v[to][j] == 1)
s++;
if(s != vv.size())
return 0;
}
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() && l + r > 0){
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 : حسن