제출 #431308

#제출 시각아이디문제언어결과실행 시간메모리
431308Blistering_Barnacles슈퍼트리 잇기 (IOI20_supertrees)C++14
96 / 100
306 ms35200 KiB
#include "supertrees.h" #include <vector> //apig's property //Happiness can be found, even in the darkest of times, if one only remembers to turn on the light //El Pueblo Unido Jamas Sera Vencido //The saddest thing about betrayal? is that it never comes from your enemies //Do or do not... there is no try //Billions of bilious blue blistering barnacles in a thundering typhoon! #include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) #define F first #define S second #define pb push_back #define vll vector< ll > #define vi vector< int > #define pll pair< ll , ll > #define pi pair< int , int > #define all(s) s.begin() , s.end() #define sz(s) s.size() #define str string #define md ((s + e) / 2) #define mid ((l + r) / 2) #define msdp(dp) memset(dp , -1 , sizeof dp) #define mscl(dp) memset(dp , 0 , sizeof dp) #define C continue #define R return #define B break #define lx node * 2 #define rx node * 2 + 1 #define br(o) o ; break #define co(o) o ; continue using namespace std; typedef int ll; ll q, par1[100005], a[555555] , par2[555555] , k, l, m, n, o, p; map < ll , ll > mp; const ll mod = 1e9+7; str s; vector < vll > ans ; vll adj[555555] ; ll getpar1(ll x){ R (x == par1[x] ? x : par1[x] = getpar1(par1[x])) ; } void mrg1(ll x ,ll y){ x = getpar1(x) , y = getpar1(y) ; if(x == y)R ; par1[y] = x ; } ll getpar2(ll x){ R (x == par2[x] ? x : par2[x] = getpar2(par2[x])) ; } void mrg2(ll x , ll y){ x = getpar2(x) , y = getpar2(y) ; if(x == y)R ; par2[y] = x ; } int construct(vector<vector<int>> p) { n = sz(p) ; ans.resize(n) ; for(ll i = 0 ; i < n ; i++){ if(p[i][i] != 1)R 0 ; ans[i].resize(n) ; par1[i] = par2[i] = i ; } for(ll i = 0 ; i < n ; i++){ for(ll j = i + 1 ; j < n ; j++){ if(p[i][j] == 1)mrg1(i , j) ; else if(p[i][j] == 2)mrg2(i , j) ; } } for(ll i = 0 ; i < n ; i++){ if(par1[i] == i){ ll op = getpar2(i) ; adj[op].pb(i) ; C ; } ll op = getpar1(i) ; ans[op][i] = ans[i][op] = 1 ; } for(ll i = 0 ; i < n ; i++){ m = sz(adj[i]) ; if(m <= 1)C ; if(m == 2)R 0 ; for(ll j = 0 ; j < m ; j++){ ll j1 = adj[i][j] , j2 = adj[i][(j + 1) % m] ; //cout << j1 << " " << j2 << endl ; ans[j1][j2] = ans[j2][j1] = 1 ; } } for(ll i = 0; i < n ; i++){ for(ll j = i + 1 ; j < n ; j++){ ll o1 = getpar1(i) , o2 = getpar1(j) ; if(o1 == o2 && p[i][j] != 1)R 0 ; ll o3 = getpar2(i) , o4 = getpar2(j) ; if(p[i][j] == 0 && (o1 == o2 || o3 == o4))R 0 ; if(p[i][j] == 2 && o1 == o2)R 0 ; } } for(ll i = 0 ; i < n ; i++)ans[i][i] = 0 ; build(ans) ; R 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...