제출 #604524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604524		Theo830	Newspapers (CEOI21_newspapers)	C++17	100 / 100	83 ms	43764 KiB

newspapers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
bool ok = 1;
vector<vll>adj;
vll res;
ll c[1005] = {0};
void solve(ll idx,ll p){
    res.pb(idx+1);
    bool f = 1;
    ll posa = 0;
    for(auto x:adj[idx]){
        if(x != p){
            if(f){
                f = 0;
            }
            else{
                res.pb(idx+1);
            }
            c[x] = c[idx] ^ 1;
            solve(x,idx);
            posa += adj[x].size() != 1;
        }
    }
    if(posa > 1){
        ok = 0;
    }
}
bool cmp(ll a,ll b){
    return adj[a].size() < adj[b].size();
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    adj.assign(n+5,vll());
    ll deg[n] = {0};
    vector<ii>ed;
    vll ans;
    f(i,0,5000){
        ans.pb(i);
    }
    f(i,0,m){
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        deg[a]++;
        deg[b]++;
        ed.pb(ii(a,b));
    }
    ok = m == n-1;
    vll w[n];
    if(ok){
        for(auto x:ed){
            if(deg[x.F] != 1 && deg[x.S] != 1){
                adj[x.F].pb(x.S);
                adj[x.S].pb(x.F);
            }
        }
        f(i,0,n){
            sort(all(adj[i]),cmp);
        }
        bool ivra = 0;
        f(i,0,n){
            f(j,0,5000){
                w[i].pb(j);
            }
        }
        f(i,0,n){
            if(deg[i] != 1){
                res.clear();
                ok = 1;
                solve(i,-1);
                if(ok){
                    w[i] = res;
                }
                if(ok && res.size() < ans.size()){
                    ans = res;
                }
                ivra |= ok;
            }
        }
        ok = ivra;
    }
    if(n == 1){
        cout<<"YES\n";
        cout<<"1\n 1\n";
    }
    else if(n == 2){
        cout<<"YES\n";
        cout<<"2\n2 2\n";
    }
    else if(ok){
        cout<<"YES\n";
        bool ek = (ans.size() % 2);
        f(i,0,n){
            if(c[i] != c[ans[0]-1] && w[i].size() == ans.size()){
                ek = 1;
                break;
            }
        }
        cout<<2 * ans.size() + (ek == 0)<<"\n";
        for(auto x:ans){
            cout<<x<<" ";
        }
        if(ans.size() % 2 == 0){
            ek = 0;
            f(i,0,n){
                if(c[i] != c[ans[0]-1] && w[i].size() == ans.size()){
                    ans = w[i];
                    ek = 1;
                    break;
                }
            }
            if(!ek){
                ans.insert(ans.begin(),1);
            }
        }
        for(auto x:ans){
            cout<<x<<" ";
        }
    }
    else{
        cout<<"NO\n";
    }
}

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