Submission #347147

#TimeUsernameProblemLanguageResultExecution timeMemory
347147Dilshod_ImomovConnecting Supertrees (IOI20_supertrees)C++17
56 / 100
274 ms26400 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int N = 1e3 + 7; vector < int > adj[N], visited(N); bool first[N]; void dfs( int v ) { visited[v] = 1; for ( auto u: adj[v] ) { if ( !visited[u] ) { dfs(u); } } } int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } for ( int i = 0; i < n; i++ ) { for ( int j = 0; j < n; j++ ) { if ( i == j ) { continue; } if ( p[i][j] == 1 ) { adj[i].push_back(j); } } } vector < int > comp, used(n + 7); for ( int i = 0; i < n; i++ ) { if ( visited[i] ) { continue; } for ( auto j: adj[i] ) { visited[j] = 1; } comp.push_back(i); } for ( int i = 0; i < n; i++ ) { if ( used[i] ) { continue; } used[i] = 1; for ( auto j: adj[i] ) { answer[i][j] = 1; used[j] = 1; answer[j][i] = 1; for ( auto k: adj[i] ) { if ( j != k && p[j][k] != 1 ) { return 0; } } } } int sz = comp.size(); used = vector < int > (n + 7); for ( int i = 0; i < sz; i++ ) { vector < int > vc = { comp[i] }; if ( used[ comp[i] ] ) { continue; } used[ comp[i] ] = i + 1; for ( int j = 0; j < sz; j++ ) { if ( i != j && p[ comp[i] ][ comp[j] ] == 2 ) { vc.push_back(comp[j]); used[ comp[j] ] = i + 1; } } for ( auto v: vc ) { for ( int j = 0; j < sz; j++ ) { int u = comp[j]; if ( v != u && p[ v ][u] == 0 ) { for ( auto x: adj[v] ) { for ( auto y: adj[u] ) { if ( p[x][y] ) { return 0; } } } } } } int szz = vc.size(); for ( int i = 0; i < szz; i++ ) { for ( int j = 0; j < szz; j++ ) { if ( i == j ) { continue; } if ( p[ vc[i] ][ vc[j] ] != 2 ) { return 0; } int v = vc[i], u = vc[j]; for ( auto x: adj[v] ) { for ( auto y: adj[u] ) { if( p[x][y] != 2 ) { return 0; } } } } } for ( int i = 0; i < szz - 1; i++ ) { answer[vc[i]][vc[i + 1]] = 1; answer[ vc[i + 1] ][ vc[i] ] = 1; } if ( szz > 1 ) { answer[ vc[szz - 1] ][ vc[0] ] = 1; answer[ vc[ 0 ] ][ vc[szz - 1] ] = 1; } } build(answer); 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...