Submission #533950

#	Time	Username	Problem	Language	Result	Execution time	Memory
533950		AbrahamJ	Newspapers (CEOI21_newspapers)	C++98	100 / 100	20 ms	416 KiB

newspapers

    #include <bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
    vector<int> adj[1010];
    int h[1010], c[1010];
    bool L[1010];
     
    void NO(){
        printf("NO\n");
        exit(0);
    }
     
    void dfs0(int s, int pa = -1){
        h[s] = 1;
        if (pa==-1) c[s] = 0;
        L[s] = 1;
        for (auto &v:adj[s]) if (v!=pa){
            L[s] = 0;
            c[v] = c[s] ^ 1;
            dfs0(v, s);
     
            h[s] = max(h[s], h[v] + 1);
        }
    }
     
    int r = -1;
    void chk_valid(int n){
        for (int i=1;i<=n;i++){
            dfs0(i);
            int cnt = 0;
            for (auto &v:adj[i]) if (h[v]>=3) cnt++;
            if (cnt>=3) NO();
            if (cnt==2) r = i;
        }
    }
     
    vector<int> st;
    void dfs2(int s, int pa){
        if (L[s]) return;
        bool flag = 0;
        for (auto &v:adj[s]) if (v!=pa && !L[v]){
            st.push_back(s);
            dfs2(v, s);
            flag = 1;
        }
        if (!flag) st.push_back(s);
    }
     
    bool cmp(int x, int y){return h[x] > h[y];}
     
     
    int main(){
        int n, m;
        scanf("%d %d", &n, &m);
        if (m>n-1) NO();
        if (n<=2){
            //naive here
            if (n==1) printf("YES\n1\n1\n");
            else printf("YES\n2\n1 1\n");
            return 0;
        }
     
        for (int i=0;i<m;i++){
            int x, y;
            scanf("%d %d", &x, &y);
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
     
        chk_valid(n);
     
        if (r==-1){
            for (int i=1;i<=n;i++) if (adj[i].size()>=2) r = i;
        }
        assert(r!=-1);
        //printf("R = %d\n", r);
     
        dfs0(r);
        for (int i=1;i<=n;i++) sort(adj[i].begin(), adj[i].end(), cmp);
        if (adj[r].size()>=2 && h[adj[r][1]]>=3) swap(adj[r][1], adj[r].back());
        for (int i=1;i<=n;i++) reverse(adj[i].begin(), adj[i].end());
     
        vector<int> ans;
        for (auto &v:adj[r]){
            if (h[v]>=3 && v==adj[r].back() && (ans.empty() || ans.back()!=r)) ans.push_back(r);
     
            st.clear();
            dfs2(v, r);
     
            if (h[v]>=3 && v!=adj[r].back()) reverse(st.begin(), st.end());
            for (auto &x:st) ans.push_back(x);
     
            if (h[v]==2 || (h[v]>=3 && v!=adj[r].back())){
                ans.push_back(r);
                //printf("asdf\n");
            }
        }
     
        if (ans.empty()) ans.push_back(r);
        bool inv = (c[ans[0]]!=c[ans.back()]);
     
        printf("YES\n");
        printf("%d\n", (int)ans.size()*2);
        for (auto &x:ans) printf("%d ", x);
        if (inv) reverse(ans.begin(), ans.end());
        for (auto &x:ans) printf("%d ", x);
        return 0;
    }

Compilation message (stderr)

newspapers.cpp: In function 'int main()':
newspapers.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d %d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~
newspapers.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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