Submission #1166274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166274		ByeWorld	Newspapers (CEOI21_newspapers)	C++20	50 / 100	127 ms	15880 KiB

newspapers

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int SQRT = 300;
const int MAXA = 50;
const int LOG = 20;
const int INF = 1e18+10;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, m;
vector <int> adj[MAXN];
int mx=0;

void dfs(int nw, int par, int dis){
    chmx(mx, dis);
    for(auto nx : adj[nw]){
        if(nx==par) continue;
        dfs(nx,nw,dis+1);
    }
}
bool solve(){
    if(m!=n-1) return 0;
    bool can = 1;
    for(int i=1; i<=n; i++){
        int cnt = 0;
        for(auto nx : adj[i]){
            mx=0;
            dfs(nx,i,1);
            if(mx>=3) cnt++;
        }
        if(cnt>=3) can = 0;
    }
    return can;
}
signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y; cin>>x>>y;
        adj[x].pb(y); adj[y].pb(x);
    }
    if(solve()){
        cout << "YES\n1\n1\n";
    }
    else cout << "NO\n";
}
/*

    if(m==n-1){
        int num = 0, id = -1;
        for(int i=1; i<=n; i++)
            if(adj[i].size() >= 3) num++, id = i;
        if(num>=2){
            cout << "NO\n"; exit(0);
        } else if(num==1){
            bool can = 1;
            for(int i=1; i<=n; i++){
                if(i == id) continue;
                if(adj[i].size() >= 2) can = 0;
            }
            if(can){
                cout << "YES\n2\n"; cout<<id<<' '<<id<<'\n';
            } else cout << "NO\n";
            exit(0);
        }

        if(n==1){
            cout << "YES\n1\n1\n";
            exit(0);
        }
        if(n<=3){
            cout << "YES\n2\n2 2\n"; exit(0);
        }
        cout << "YES\n";
        cout << 2*(n-2) << '\n';
        for(int i=2; i<=n-1; i++) cout << i << ' ';
        for(int i=n-1; i>=2; i--) cout << i << ' ';
        cout << '\n';
    } else {
        cout << "NO\n";
    }
    */

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