Submission #957242

#TimeUsernameProblemLanguageResultExecution timeMemory
957242LucaIlieNewspapers (CEOI21_newspapers)C++17
100 / 100
150 ms4440 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e3; int n; int depth[MAX_N + 1], parent[MAX_N + 1], maxDepth[MAX_N + 1], lf[MAX_N + 1], sizee[MAX_N + 1]; vector<int> adj[MAX_N + 1]; int findCentroid( int u, int p ) { int c = 0, mx = 0; sizee[u] = 1; for ( int v: adj[u] ) { if ( v == p ) continue; int x = findCentroid( v, u ); if ( x != 0 ) c = x; sizee[u] += sizee[v]; mx = max( mx, sizee[v] ); } mx = max( mx, n - sizee[u] ); if ( mx <= n / 2 ) c = u; return c; } bool ok = true; void check( int u, int p ) { depth[u] = depth[p] + 1; maxDepth[u] = depth[u]; int c = 0; for ( int v: adj[u] ) { if ( v == p ) continue; check( v, u ); maxDepth[u] = max( maxDepth[u], maxDepth[v] ); if ( maxDepth[v] - depth[u] > 2 ) c++; } if ( (depth[u] >= 3 && c >= 2) || (c >= 3) ) ok = false; } bool isOnDiam[MAX_N + 1]; vector<int> diam; int diamLen = 0, x = 0, y = 0, l = 0; void dfs( int u, int p ) { int mx1 = -1, a = u, mx2 = -1, b = 0; parent[u] = p; for ( int v: adj[u] ) { if ( v == p ) continue; dfs( v, u ); if ( depth[v] > mx1 ) { mx2 = mx1; b = a; mx1 = depth[v]; a = lf[v]; } else if ( depth[v] > mx2 ) { mx2 = depth[v]; b = lf[v]; } } depth[u] = mx1 + 1; lf[u] = a; if ( mx1 + mx2 + 2 > diamLen ) { diamLen = mx1 + mx2 + 2; x = a; y = b; l = u; } //printf( "%d %d %d %d\n", u, mx1, mx2, depth[u] ); } int main() { int m; cin >> n >> m; for ( int i = 0; i < m; i++ ) { int u, v; cin >> u >> v; adj[u].push_back( v ); adj[v].push_back( u ); } if ( m != n - 1 ) { cout << "NO\n"; return 0; } if ( n == 1 ) { cout << "YES\n1\n1\n"; return 0; } if ( n <= 3 ) { cout << "YES\n2\n2 2\n"; return 0; } int c = findCentroid( 1, 0 ); check( c, 0 ); if ( !ok ) { cout << "NO\n"; return 0; } dfs( c, 0 ); while ( x != l ) { diam.push_back( x ); isOnDiam[x] = true; x = parent[x]; } diam.push_back( l ); isOnDiam[l] = true; vector<int> a; while ( y != l ) { a.push_back( y ); isOnDiam[y] = true; y = parent[y]; } reverse( a.begin(), a.end() ); for ( int u: a ) diam.push_back( u ); vector<int> sol; for ( int i = 1; i <= diam.size() - 2; i++ ) { int v = diam[i]; sol.push_back( v ); for ( int u: adj[v] ) { if ( isOnDiam[u] || adj[u].size() == 1 ) continue; sol.push_back( u ); sol.push_back( v ); } } reverse( diam.begin(), diam.end() ); for ( int i = 1; i <= diam.size() - 2; i++ ) { int v = diam[i]; sol.push_back( v ); for ( int u: adj[v] ) { if ( isOnDiam[u] || adj[u].size() == 1 ) continue; sol.push_back( u ); sol.push_back( v ); } } cout << "YES\n"; cout << sol.size() << "\n"; for ( int v: sol ) cout << v << " "; return 0; }

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:134:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for ( int i = 1; i <= diam.size() - 2; i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~
newspapers.cpp:145:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for ( int i = 1; i <= diam.size() - 2; i++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...