oj.uz

Submission #1037167

# Submission time Handle Problem Language Result Execution time Memory
1037167 2024-07-28T09:45:24 Z Dzadzo Newspapers (CEOI21_newspapers) C++14
0 / 100
 1 ms 2652 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<ll,ll>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<pii>
#define vvp vector<vp>
#define vb vector<bool>
#define vvb vector<vb>
#define INF 1000000000000000
#define MOD 1000000007
#define MAXN 100000
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
vvi adj(MAXN+1);
pii best;
vi arr;
void find(int v,int p,int p1,int dist) {
    for (int to:adj[v])
        if (to!=p && to!=p1)
            find(to,v,0,dist+1);
    best=max(best,{dist,v});
}
bool found=false;
void getpath(int v,int p,int u) {
    if (found)return;
    arr.pb(v);
    if (v==u) {
        found=true;
        return;
    }
    for (int to:adj[v])
        if (to!=p)
            getpath(to,v,u);
    if (!found)arr.pop_back();
}
signed main() {
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    if (m!=n-1)cout<<"NO\n",exit(0);
    if (n==1) {
        cout<<"1\n1";
        exit(0);
    }
    if (n==2) {
        cout<<"2\n1 1";
        exit(0);
    }
    find(1,0,0,0);
    int U=best.S;
    best={0,0};
    find(U,0,0,0);
    int V=best.S;
    getpath(V,0,U);

    vi ans;
    bool res=true;
    for (int i=1;i<arr.size()-1;i++) {
        best={0,0};
        find(arr[i],arr[i-1],arr[i+1],0);
        if (best.F>2)res=false;
        ans.pb(arr[i]);
        for (int x:adj[arr[i]])if (x!=arr[i-1] && x!=arr[i+1])ans.pb(x);
    }
    if (!res)cout<<"NO\n",exit(0);
    
    cout<<"YES\n";
    cout<<ans.size()*2<<"\n";
    for (int x:ans)cout<<x<<" ";
    ans.clear();
    reverse(arr.begin(),arr.end());
    for (int i=1;i<arr.size()-1;i++) {
        best={0,0};
        find(arr[i],arr[i-1],arr[i+1],0);
        if (best.F>2)res=false;
        ans.pb(arr[i]);
        for (int x:adj[arr[i]])if (x!=arr[i-1] && x!=arr[i+1])ans.pb(x);
    }
    for (int x:ans)cout<<x<<" ";


}


/*
8 7
1 2
1 3
2 4
2 5
2 8
5 6
5 7
*/

Compilation message

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

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Token "1" doesn't correspond to pattern "YES|NO"
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Token "1" doesn't correspond to pattern "YES|NO"
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB Token "1" doesn't correspond to pattern "YES|NO"
2 Halted 0 ms 0 KB -