Submission #1108587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108587		razivo	Newspapers (CEOI21_newspapers)	C++14	4 / 100	2 ms	588 KiB

newspapers

#include <iostream>
#include <vector>
using namespace  std;
int ct = 0;
vector<int> res;
vector<bool> b;
bool dfs(int c, int p,vector<vector<int>> &g) {
    res.push_back(c);
    ct++;
    int r = true;
    int coun = 0;
    bool h = false;
    for(auto i:g[c]) {
        if(g[i].size()==1) h=true;
    }
    if(h) ct++;
    b.push_back(h);
    for(auto i:g[c]) {
        if(i==p) continue;
        if(g[i].size()==1) continue;
        r&=dfs(i,c,g);
        coun++;
    }
    if(coun>1) return false;

    return r;
}
int main()
{
    int n,m; cin>>n>>m;
    if(m!=n-1) {
        cout<<"NO"<<endl;
        exit(0);
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int x,y; cin>>x>>y; x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if(n==2) {
        cout<<"YES"<<endl;
        cout<<"2"<<endl;
        cout<<"1 1"<<endl;
        exit(0);
    }
    int cur = 0;
    while(true) {
        if(cur==n) break;
        if(g[cur].size()==1) {cur++; continue;}
        int coun = 0;
        for(int i : g[cur]) if(g[i].size()!=1) coun++;
        if(coun==1) break;
        cur++;
    }
    if(cur==n) {
        cur = 0;
        while(true) {
            if(g[cur].size()!=1) break;
            cur++;
        }
        cout<<"YES"<<endl;
        cout<<2<<endl;
        cout<<(cur+1)<< " "<<(cur+1)<<endl;
    }else {
        if(!dfs(cur,-1,g)) {
            cout<<"NO"<<endl;
        }else {
            cout<<"YES"<<endl;
            cout<<res.size()*2<<endl;
            for (int i = 0; i < res.size()-1; ++i) {
                cout<<res[i]+1<<" ";
                if(true) cout<<res[i]+1<<" ";
            }
            cout<<res[res.size()-1]+1;
            if(true) cout<<" "<<res[res.size()-1]+1;
            cout<<endl;
        }
    }
}

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:71:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for (int i = 0; i < res.size()-1; ++i) {
      |                             ~~^~~~~~~~~~~~~~

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