oj.uz

Submission #1108583

# Submission time Handle Problem Language Result Execution time Memory
1108583 2024-11-04T13:57:57 Z razivo Newspapers (CEOI21_newspapers) C++14
4 / 100
 2 ms 588 KB 
#include <iostream>
#include <vector>
using namespace  std;
int ct = 0;
vector<int> res;
vector<bool> b;
bool dfs(int c, int p,vector<vector<int>> &g) {
    res.push_back(c);
    ct++;
    int r = true;
    int coun = 0;
    bool h = false;
    for(auto i:g[c]) {
        if(g[i].size()==1) h=true;
    }
    if(h) ct++;
    b.push_back(h);
    for(auto i:g[c]) {
        if(i==p) continue;
        if(g[i].size()==1) continue;
        r&=dfs(i,c,g);
        coun++;
    }
    if(coun>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<<"2"<<endl;
        cout<<"1 1"<<endl;
        exit(0);
    }
    int cur = 0;
    while(true) {
        if(cur==n) break;
        if(g[cur].size()==1) {cur++; continue;}
        int coun = 0;
        for(int i : g[cur]) if(g[i].size()!=1) coun++;
        if(coun==1) break;
        cur++;
    }
    if(cur==n) {
        cur = 0;
        while(true) {
            if(g[cur].size()!=1) break;
            cur++;
        }
        cout<<"YES"<<endl;
        cout<<2<<endl;
        cout<<(cur+1)<< " "<<(cur+1)<<endl;
    }else {
        if(!dfs(cur,-1,g)) {
            cout<<"NO"<<endl;
        }else {
            cout<<"YES"<<endl;
            cout<<ct<<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:71:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for (int i = 0; i < res.size()-1; ++i) {
      |                             ~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Provide a successful but not optimal strategy.
2 Correct 1 ms 336 KB Output is correct
3 Partially correct 1 ms 504 KB Failed to provide a successful strategy.
4 Partially correct 1 ms 504 KB Failed to provide a successful strategy.
5 Correct 1 ms 336 KB Output is correct
6 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 504 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
4.0 / 8.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Provide a successful but not optimal strategy.
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
5 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
6 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
7 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
8 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
9 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
10 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
11 Partially correct 2 ms 336 KB Failed to provide a successful strategy.
12 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
13 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
14 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
15 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
16 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
17 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
18 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
19 Partially correct 1 ms 588 KB Failed to provide a successful strategy.
20 Partially correct 1 ms 336 KB Failed to provide a successful strategy.

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Provide a successful but not optimal strategy.
2 Correct 1 ms 336 KB Output is correct
3 Partially correct 1 ms 504 KB Failed to provide a successful strategy.
4 Partially correct 1 ms 504 KB Failed to provide a successful strategy.
5 Correct 1 ms 336 KB Output is correct
6 Partially correct 1 ms 336 KB Failed to provide a successful strategy.
7 Correct 1 ms 336 KB Output is correct
8 Incorrect 1 ms 504 KB Output isn't correct
9 Halted 0 ms 0 KB -