Submission #957242

#	Time	Username	Problem	Language	Result	Execution time	Memory
957242		LucaIlie	Newspapers (CEOI21_newspapers)	C++17	100 / 100	150 ms	4440 KiB

newspapers

#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++ ) {
      |                      ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 8 / 8
• Subtask 3: 80 / 80