Submission #1011941

#TimeUsernameProblemLanguageResultExecution timeMemory
1011941LucaIlieConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
131 ms22180 KiB
#include "supertrees.h" #include <vector> #include <iostream> using namespace std; vector<vector<int>> answer; #define nmax 1000 int daddy[nmax], daddy_cyc[nmax]; vector<int> cyc[nmax]; int find_daddy( int a ) { int x; if( daddy[a] == a ) return a; x = find_daddy( daddy[a] ); daddy[a] = x; return x; } void marry_daddy( int a, int b ) { int x, y; x = find_daddy( a ); y = find_daddy( b ); daddy[x] = y; } int find_daddy_cyc( int a ) { int x; if( daddy_cyc[a] == a ) return a; x = find_daddy_cyc( daddy_cyc[a] ); daddy_cyc[a] = x; return x; } void marry_daddy_cyc( int a, int b ) { int x, y; x = find_daddy_cyc( a ); y = find_daddy_cyc( b ); daddy_cyc[x] = y; } int construct( vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; i++) { vector<int> row; row.resize(n); answer.push_back(row); } int i, j; bool ok = true; for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) if( p[i][j] == 3 ) ok = false; } if( !ok ) return 0; for( i = 0; i < n; i++ ) daddy[i] = daddy_cyc[i] = i; for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) if( p[i][j] == 1 ) marry_daddy( i, j ); } for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) if( p[i][j] != 1 && find_daddy(i) == find_daddy(j) ) ok = false; } if( !ok ) return 0; for( i = 0; i < n; i++ ) if( find_daddy(i) != i ) { answer[i][find_daddy(i)] = 1; answer[find_daddy(i)][i] = 1; } for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) if( p[i][j] == 2 ) marry_daddy_cyc(find_daddy(i), find_daddy(j) ); } for( i = 0; i < n; i++ ) { for( j = 0; j < n; j++ ) if( p[i][j] < 2 && find_daddy(i) != find_daddy(j) && find_daddy_cyc(find_daddy(i)) == find_daddy_cyc(find_daddy(j)) ) ok = false; } if( !ok ) return 0; for( i = 0; i < n; i++ ) { if( find_daddy_cyc(i) != i ) cyc[find_daddy_cyc(i)].push_back(i); } for( i = 0; i < n; i++ ) { if( cyc[i].size() == 1 ) ok = false; if( cyc[i].size() >= 2 ) { for( j = 0; j < cyc[i].size() - 1; j++ ) { answer[cyc[i][j+1]][cyc[i][j]] = 1; answer[cyc[i][j]][cyc[i][j+1]] = 1; } answer[i][cyc[i][0]] = 1; answer[cyc[i][0]][i] = 1; answer[i][cyc[i][j]] = 1; answer[cyc[i][j]][i] = 1; } } if( !ok ) return 0; build(answer); return 1; }

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             for( j = 0; j < cyc[i].size() - 1; j++ ) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
#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...