Submission #589555

#	Time	Username	Problem	Language	Result	Execution time	Memory
589555		jasmin	Newspapers (CEOI21_newspapers)	C++14	100 / 100	69 ms	8888 KiB

newspapers

#include<bits/stdc++.h>
using namespace std;
#define int long long 

pair<int,int> farthest(int v, vector<vector<int> >& adi, vector<int>& p){

    pair<int,int> mmax={0, v};
    for(auto u: adi[v]){
        if(u!=p[v]){
            p[u]=v;
            mmax=max(mmax, farthest(u, adi, p));
        }
    }
    return {mmax.first+1, mmax.second};
}

vector<int> diameter(int n, vector<vector<int> >& adi){
    vector<int> p(n, -1);
    int root=farthest(0, adi, p).second;
    p.assign(n, -1);
    int v=farthest(root, adi, p).second;

    vector<int> d;
    d.push_back(v);
    while(v!=root){
        v=p[v];
        d.push_back(v);
    }
    return d;
}

vector<vector<int> > con;
int dfs(int v, int p, vector<vector<int> >& adi, vector<int>& next, bool & pos){
    int depth=0;

    for(auto u: adi[v]){
        if(u==p || u==next[v]) continue;
        int subtree=dfs(u, v, adi, next, pos);

        if(subtree>2) pos=false;
        if(subtree==2){
            con[v].push_back(u);
        }
        depth=max(depth, subtree);
    }

    if(next[v]!=-1){
        depth=dfs(next[v], v, adi, next, pos);
    }
    return depth+1;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int> > adi(n);
    for(int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        adi[a-1].push_back(b-1);
        adi[b-1].push_back(a-1);
    }

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

    vector<int> d=diameter(n, adi);
    vector<int> next(n, -1);
    for(int i=0; i<d.size()-1; i++){
        next[d[i]]=d[i+1];
    }

    con.resize(n);
    bool pos=true;
    dfs(d[0], -1, adi, next, pos);
    vector<int> a;
    for(int i=1; i<d.size()-1; i++){
        int v=d[i];
        a.push_back(v);

        for(auto u: con[v]){
            a.push_back(u);
            a.push_back(v);
        }
    }

    if(pos){
        cout << "YES\n";
        if(n==1){
            cout << 1 << "\n" << 1 << "\n";
            return 0;
        }
        else if(n==2){
            cout << 2 << " \n" << 1 << " " << 1 << "\n";
            return 0;
        }

        cout << 2*a.size() << "\n";
        for(int i=0; i<a.size(); i++){
            cout << a[i]+1 << " ";
        }
        for(int i=a.size()-1; i>=0; i--){
            cout << a[i]+1 << " ";
        }
        cout << "\n";
    }
    else{
        cout << "NO\n";
    }
}

Compilation message (stderr)

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

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