Submission #1097498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097498		alexander707070	Newspapers (CEOI21_newspapers)	C++14	50 / 100	132 ms	22340 KiB

newspapers

#include<bits/stdc++.h>
#define MAXN 600007
using namespace std;

int n,m,a,b;
vector<int> v[MAXN];

bool dfs(int x,int p,int dep){
    if(dep==1)return true;
    
    for(int i:v[x]){
        if(i==p)continue;
        if(dfs(i,x,dep-1))return true;
    }

    return false;
}

int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

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

    for(int i=1;i<=n;i++){
        if(v[i].size()<=2)continue;

        int br=0;
        for(int f:v[i]){
            if(dfs(f,i,3))br++;
        }

        if(br>2){
            cout<<"NO\n";
            return 0;
        }
    }

    cout<<"YES\n1\n1\n";

    return 0;
}

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