Submission #940826

#	Time	Username	Problem	Language	Result	Execution time	Memory
940826		berr	Newspapers (CEOI21_newspapers)	C++17	100 / 100	113 ms	47476 KiB

newspapers

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
 
    vector<vector<int>> g(n);
    vector<int> d(n), val(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);
    }
 
    int flag = 1;
 
    auto dfs=[&](int v, int p, auto&&dfs)->int{
        if(v==p) d[v]=0;
        else d[v]=d[p]+1;
 
        val[v] = d[v];
 
        vector<int> a;
        for(auto i: g[v]){  
            if(i!=p) a.push_back(dfs(i, v, dfs));
        }
 
        sort(a.begin(), a.end());
/*        sort(g[v].begin(), g[v].end(), [&](int x, int y){
            return val[x]<val[y];
        });*/
 
        if(a.size())
        val[v]=max(val[v], a.back());
 
        if(v==p){
            if(a.size()>2 && a[a.size()-3] >2) flag =0;
        }
        return val[v];
          
    };
 
    if(n==m+1)
    for(int i=0; i<n; i++) dfs(i, i, dfs);
    else flag =0;
 
    if(flag){ 
        cout<<"YES\n";
        if(n==1) cout<<1<<" "<<1<<"\n";
        else if(n==2) cout<<"2 2 2"<<"\n";
        else{
            int check = 1;
            vector a(n, vector(n, vector<int>()));
            vector vis(n, vector(n, 0));
 
            auto dfs2=[&](int v, int p, auto&&dfs2)->vector<int>{
                vector<int> s; 
                if(vis[v][p]) return a[v][p];
                vis[v][p]=1;
             //   cout<<v<<" "<<d[v]<<" "<<val[v]<<"\n";
                if(d[v]==val[v]) return a[v][p]=s;
                else if(d[v]>=val[v]-1){
                    s.push_back(v);
                    return a[v][p]=s;
                }            
                else{
                    vector<int> b;
                    vector<vector<int>> c;
 
                    for(auto i: g[v]){
                        if(i==p) continue;
 
                        c.push_back(dfs2(i, v, dfs2));
                    }
 
          
                    sort(c.begin(), c.end(), [&](auto x, auto y){
                        return x.size()<y.size();
                    });
 
                    if(!c.back().size()){
                        return b;
                    }
 
                    
 
                    if(c.size()>1){
                        int k = c.size()-2;
                        reverse(c[k].begin(), c[k].end());
                    }   
 
      
                    if(v!=p){
                         for(auto i: c.back()) b.push_back(i);
                        b.push_back(v);
                        for(int i=0; i<c.size()-1; i++){
     
                            if(!c[i].size()){
                                continue;
                            }
                            for(auto j: c[i]){
                                b.push_back(j);
                            }
                            b.push_back(v);
     
     
                        }
                    }
                    else{
                        for(auto i: c.back()) b.push_back(i);
                        b.push_back(v);
 
                        for(int i=0; i<c.size()-1; i++){
     
                            if(!c[i].size()){
                                continue;
                            }
                            for(auto j: c[i]){
                                b.push_back(j);
                            }
                            if(i!=c.size()-2)
                            b.push_back(v);
     
     
                        }
                    }
                    
                    if(v!=p){
                        if(c.size()>=2 && c[c.size()-2].size()>1) check=0;
                    }
 
                    return a[v][p]=b;
                }
            };
 
            vector<int> x;
 
            for(int i=0; i<n; i++){
                dfs(i, i, dfs);
                check = 1;
                auto s = dfs2(i, i, dfs2);
                if(!x.size()&&check) x = s;
                else if(s.size()<x.size()&&check) x = s; 
            }
 
           // reverse(x.begin(), x.end());
 
            for(int i=x.size()-1; i>=0; i--){
                x.push_back(x[i]);
            }
 
            cout<<x.size()<<"\n";
 
            for(auto i: x) cout<<i+1<<" ";
                cout<<"\n";
 
 
        } 
    }
    else cout<<"NO\n";
 
}

Compilation message (stderr)

newspapers.cpp: In lambda function:
newspapers.cpp:101:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |                         for(int i=0; i<c.size()-1; i++){
      |                                      ~^~~~~~~~~~~
newspapers.cpp:118:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                         for(int i=0; i<c.size()-1; i++){
      |                                      ~^~~~~~~~~~~
newspapers.cpp: In instantiation of 'main()::<lambda(long long int, long long int, auto:24&&)> [with auto:24 = main()::<lambda(long long int, long long int, auto:24&&)>&]':
newspapers.cpp:146:41:   required from here
newspapers.cpp:101:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |                         for(int i=0; i<c.size()-1; i++){
      |                                      ~^~~~~~~~~~~
newspapers.cpp:118:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                         for(int i=0; i<c.size()-1; i++){
      |                                      ~^~~~~~~~~~~
newspapers.cpp:126:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |                             if(i!=c.size()-2)
      |                                ~^~~~~~~~~~~~

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