oj.uz

Submission #1108580

# Submission time Handle Problem Language Result Execution time Memory
1108580 2024-11-04T13:53:37 Z razivo Newspapers (CEOI21_newspapers) C++14
0 / 100
 1 ms 336 KB 
#include <iostream>
#include <vector>
using namespace  std;
vector<int> res;
vector<bool> b;
bool dfs(int c, int p,vector<vector<int>> &g) {
    res.push_back(c);
    int r = true;
    int count = 0;
    bool h = false;
    for(auto i:g[c]) {
        if(g[i].size()==1) h=true;
    }
    b.push_back(h);
    for(auto i:g[c]) {
        if(i==p) continue;
        if(g[i].size()==1) continue;
        r&=dfs(i,c,g);
        count++;
    }
    if(count>1) return false;

    return r;
}
int main()
{
    int n,m; cin>>n>>m;
    if(m!=n-1) {
        cout<<"NO"<<endl;
        exit(0);
    }
    vector<vector<int>> g(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);
    }
    if(n==2) {
        cout<<"YES"<<endl;
        cout<<"1 1"<<endl;
        exit(0);
    }
    int cur = 0;
    while(true) {
        if(cur==n) break;
        if(g[cur].size()==1) {cur++; continue;}
        int count = 0;
        for(int i : g[cur]) if(g[i].size()!=1) count++;
        if(count==1) break;
        cur++;
    }
    if(cur==n) {
        int cur = 0;
        while(true) {
            if(g[cur].size()!=1) break;
            cur++;
        }
        cout<<"YES"<<endl;
        cout<<(cur+1)<< " "<<(cur+1)<<endl;
    }else {
        if(!dfs(cur,-1,g)) {
            cout<<"NO"<<endl;
        }else {
            cout<<"YES"<<endl;
            for (int i = 0; i < res.size()-1; ++i) {
                cout<<res[i]+1<<" ";
                if(b[i]) cout<<res[i]+1<<" ";
            }
            cout<<res[res.size()-1]+1;
            if(b[res.size()-1]) cout<<" "<<res[res.size()-1]+1;
            cout<<endl;
        }
    }
}

Compilation message

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

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
3 Incorrect 1 ms 336 KB Extra information in the output file
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
3 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
3 Incorrect 1 ms 336 KB Extra information in the output file
4 Halted 0 ms 0 KB -