oj.uz

Submission #532638

# Submission time Handle Problem Language Result Execution time Memory
532638 2022-03-03T12:31:13 Z qwerasdfzxcl Newspapers (CEOI21_newspapers) C++14
0 / 100
 1 ms 460 KB 
#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);

    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

newspapers.cpp: In function 'int main()':
newspapers.cpp:55:10: 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:14: 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
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -