oj.uz

Submission #957229

# Submission time Handle Problem Language Result Execution time Memory
957229 2024-04-03T08:44:59 Z LucaIlie Newspapers (CEOI21_newspapers) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e3;
int n;
int depth[MAX_N + 1], maxDepth[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 dfs( 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;
        dfs( 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;
}

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 <= 3 ) {
        cout << "YES\n";
        return 0;
    }


    int c = findCentroid( 1, 0 );
    dfs( c, 0 );

    if ( !ok )
        cout << "NO\n";
    else
        cout << "YES\n";

    return 0;
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -