제출 #940699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940699		berr	Newspapers (CEOI21_newspapers)	C++17	54 / 100	119 ms	47512 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{
            
            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));
                    }

                 
                    if(!c.back().size()){
                        return b;
                    }

                  /*  cout<<v+1<<"\n";
                    for(auto i: c){
                        for(auto l: i) cout<<l+1<<" ";
                            cout<<"\n";
                    }*/

                    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);


                    }
                    

                    return a[v][p]=b;
                }
            };

            vector<int> x;

            for(int i=0; i<n; i++){
                dfs(i, i, dfs);
                auto s = dfs2(i, i, dfs2);

                if(!x.size()) x = s;
                else if(s.size()<x.size()) 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";

}

컴파일 시 표준 에러 (stderr) 메시지

newspapers.cpp: In lambda function:
newspapers.cpp:95:35: 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]
   95 |                     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:116:41:   required from here
newspapers.cpp:95:35: 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]

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