Submission #558090

#	Time	Username	Problem	Language	Result	Execution time	Memory
558090		status_coding	Newspapers (CEOI21_newspapers)	C++14	50 / 100	3 ms	2772 KiB

newspapers

#include <bits/stdc++.h>

using namespace std;

int n,m;

vector<int> v[100005];

int dp[100005];

void dfs(int p, int par)
{
    dp[p] = 1;
    bool can=true;

    for(int it : v[p])
    {
        if(it == par)
            continue;

        if((int)v[it].size() == 1)
            continue;

        dfs(it, p);

        if(dp[it] == -1)
        {
            dp[p] = -1;
            return;
        }

        dp[p] = 2;

        if(dp[it] == 1)
            continue;

        if(can)
            can = false;
        else
        {
            dp[p] = -1;
            return;
        }
    }
}

int main()
{
    cin>>n>>m;

    if(m > n-1)
    {
        cout<<"NO";
        return 0;
    }

    for(int i=1;i<n;i++)
    {
        int x, y;
        cin>>x>>y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
    {
        dfs(i, 0);

        if(dp[i] != -1)
        {
            cout<<"YES\n";
            cout<<"1 1";
            return 0;
        }
    }

    cout<<"NO";
    return 0;
}

• Subtask 1: 6 / 12
• Subtask 2: 4 / 8
• Subtask 3: 40 / 80