Submission #1050035

#TimeUsernameProblemLanguageResultExecution timeMemory
1050035AlperenT_Connecting Supertrees (IOI20_supertrees)C++17
0 / 100
50 ms16680 KiB
#include "supertrees.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #define pb push_back #define F first #define S second #define all(a) a.begin(),a.end() #define pii pair <int,int> #define ld long double #define sz(v) (int)v.size() #define rep(i , a , b) for(int i=a;i <= b;i++) #define per(i, a , b) for(int i=a;i >= b;i--) using namespace std ; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 200 + 10 , sq = 333 , inf = 2e9 +100 , maxk = 2022 , mod = 1e9 + 7 ; int n , ok =1 , cnt2 = 1 , cnt = 1 , mark[maxn] ,p[maxn][maxn] , b[maxn][maxn] , c[maxn] , ye[maxn] , c2[maxn] ; vector <int> vec ; void dfs(int v){ vec.pb(v) ; c[v] = cnt ; mark[v] =1 ; rep(j , 0 ,n-1){ if(mark[j]==0 && p[v][j]){ dfs(j) ; } } } vector <int> vec2 ; void dfs2(int v){ mark[v] =1 ; c2[v] = cnt2 ; ye[cnt2] = v; for(int u : vec2){ if(mark[u]==1 || p[v][u] == 2)continue ; dfs2(u) ; } } void add(int x ,int y){ b[x][y] = b[y][x] =1 ; } bool ch(vector <int> vec){ vec2 = vec ; cnt2 = 1 ; for(int x : vec)mark[x] =0 ; for(int x : vec){ if(mark[x] == 1)continue ; dfs2(x) ; cnt2++ ; } cnt2--; for(int x : vec){ for(int y : vec){ if(c2[x] == c2[y] && p[x][y] == 2)return 0 ; } } rep(i , 1 ,cnt2){ vector <int> az ; for(int x : vec){ if(c2[x] == i)az.pb(x); } rep(j ,1 ,sz(az)-1)add(az[j-1],az[j]) ; } if(cnt2==1)return 1 ; if(cnt2 == 2){ if(sz(vec)==2)return 0 ; vector <int> a[2] ; for(int v : vec){ a[c2[v]-1].pb(v) ; } if(sz(a[0]) > sz(a[1]))swap(a[0] , a[1]) ; add(a[0][0] , a[1][0]) ; add(a[0][0] , a[1][1]) ; return 1 ; } add(ye[1],ye[cnt2]) ; rep(i ,2 , cnt2){ add(ye[i-1] , ye[i]); } return 1 ; } int construct(vector<std::vector<int>> pp) { n = sz(pp); rep(i , 0 , n-1){ rep(j , 0 ,n-1){ p[i][j] = pp[i][j] ; if(p[i][j] == 3)return 0 ; } } rep(i ,0 , n-1){ if(mark[i] == 1)continue ; dfs(i) ; cnt++; } cnt--; rep(i ,0 ,n-1){ rep(j , 0 ,n-1){ if((c[i]==c[j] && p[i][j]==0) || (c[i]!=c[j] && p[i][j]>0))return 0 ; } } rep(i , 1, cnt){ vector <int> vec; rep(j , 0 , n-1){ if(c[j] == i){ vec.pb(j) ; } } if(ch(vec)==0)return 0 ; } vector <vector <int> > bb ; rep(i , 0 , n-1){ vector <int> f ; rep(j , 0, n-1){ f.pb(b[i][j]) ; } bb.pb(f) ; } build(bb) ; return 1 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...