제출 #301850

#제출 시각아이디문제언어결과실행 시간메모리
301850infinite_iq슈퍼트리 잇기 (IOI20_supertrees)C++14
96 / 100
280 ms26392 KiB
#include <bits/stdc++.h> using namespace std ; #define pb push_back #define C continue typedef vector < int > vi ; typedef vector < vi > vivi ; #include "supertrees.h" int N ; vi v [1009] , xxx [1009] , comp ; int col [1009] , P [1009] , who [1009] , timer ; void dfs ( int node ) { if ( col [node] ) return ; col [node] = timer ; comp .pb ( node ) ; for ( auto u : v [node] ) dfs ( u ) ; } int construct(std::vector<std::vector<int>> p) { int n = p.size(); N = n ; vivi ans ; for ( int i = 0 ; i < n ; i ++ ) { vi ret ( n , 0 ) ; ans .pb ( ret ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( p [i][j] == 1 ) { v [i] .pb ( j ) ; } } } for ( int i = 0 ; i < n ; i ++ ) { if ( col [i] ) C ; timer ++ ; comp .clear () ; dfs ( i ) ; xxx [timer] = comp ; P [timer] = comp [0] ; if ( comp .size () == 1 ) C ; for ( int j = 0 ; j < ( int ) comp .size () - 1 ; j ++ ) { int a = comp [j] , b = comp [j+1] ; ans [a][b] = ans [b][a] = 1 ; } for ( auto x : comp ) { for ( auto y : comp ) { if ( p [x][y] != 1 ) return 0 ; } } } timer = 0 ; for ( int i = 0 ; i < n ; i ++ ) { who [i] = col [i] ; v [i] .clear () ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < n ; j ++ ) { if ( col [i] != col [j] && p [i][j] == 2 ) { v [P[col[i]]] .pb (P[col[j]]) ; } } } memset ( col , 0 , sizeof ( col ) ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( col [i] ) C ; timer ++ ; comp .clear () ; dfs ( i ) ; if ( comp .size () == 1 ) C ; if ( comp .size () == 2 ) return 0 ; for ( int j = 0 ; j < ( int ) comp .size () - 1 ; j ++ ) { int a = comp [j] , b = comp [j+1] ; ans [a][b] = ans [b][a] = 1 ; } int a = comp [0] , b = comp .back () ; ans [a][b] = ans [b][a] = 1 ; for ( auto x : comp ) { for ( auto y : comp ) { if ( x == y ) C ; for ( auto it1 : xxx [who[x]] ) { for ( auto it2 : xxx [who[y]] ) { if ( p [it1][it2] != 2 ) return 0 ; } } } } } build ( ans ) ; 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...