oj.uz

Submission #1008407

# Submission time Handle Problem Language Result Execution time Memory
1008407 2024-06-26T11:34:51 Z cow123 Newspapers (CEOI21_newspapers) C++14
60 / 100
 3 ms 648 KB 
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i = a; i < b;++i)
#define pb emplace_back
using namespace std;
const int maxn = 1005;
vector<int> V[maxn],odp;
int vis[maxn],vis1[maxn],mark[maxn];
void dfs(int v){
    for(auto y : V[v]){
        if(mark[y] == 0 && vis[y] == 0 && V[y].size() > 1){
            vis[y] = 1;
            odp.pb(y);
            odp.pb(v);            
        }
    }
    for(auto y : V[v]){
        if(mark[y] == 1 && vis[y] == 0){
            vis[y] = 1;
            odp.pb(y);
            dfs(y);
        }
    }
}
int d1 = 0;
void dyst(int v){
    for(auto y : V[v]){
        if(vis[y] == 0){
            vis[y] = vis[v] + 1;
            d1 = max(d1,vis[y]);
            dyst(y);
            
        }
    }
}
int main(){
    int n,m;
    cin>>n >>m;
    if(m > n - 1){ //cykl
        cout<<"NO";
        return 0;
    }
    if(n == 1){
        cout<<"YES" <<"\n" <<1 <<"\n" <<1;
        return 0;
    }
    if(n == 2){
        cout<<"YES" <<"\n" <<2 <<"\n" <<1 <<" " <<1;
        return 0;
    }
    
    FOR(i,0,m){
        int x,y;
        cin>>x >>y;
        V[x].pb(y);
        V[y].pb(x);
    }
    FOR(i,1,n + 1){
        if(V[i].size() >= 3){
            FOR(j,0,n + 1){
                vis[j] = 0; 
            }
            vis[i] = 1;
            int cnt = 0;
            for(auto y : V[i]){
                vis[y] = 1;
                  d1 = 0;
                  dyst(y);
                if(d1 >= 3){
                    ++cnt;
                } 
            }
            if(cnt >= 3){ 
                cout<<"NO";
                return 0;
            }
        }
    }
    
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    d1 = 0;
    int y1 = 0;
    vis[1] = 1;
    dyst(1);
    FOR(i,1,n + 1){
        if(vis[i] == d1){
            y1 = i;
        }
    
    }
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    d1 = 0;
    vis[y1] = 1;
    dyst(y1);
    FOR(i,1,n + 1){
        if(vis[i] == d1){
            y1 = i;
        }
    }
    FOR(i,0,n + 1){
        vis1[i] = vis[i];
        vis[i] = 0;
    }
    d1 = 0;
    vis[y1] = 1;
    dyst(y1);
    int x2 = 0;
    FOR(i,0,n + 1){
        if(vis[i] + vis1[i] == d1 + 1 && V[i].size() > 1){
            mark[i] = 1;
        }
    }
    FOR(i,0,n + 1){
        vis[i] = 0;
    }
    FOR(i,0,n + 1){
        if(V[i].size() > 1 && mark[i] == 1){
            x2 = i;
        }
    }
    odp.pb(x2);
    vis[x2] = 1;
    dfs(x2);
    cout<<"YES" <<"\n" <<odp.size() * 2 <<"\n";
    for(auto y : odp){
        cout<<y <<" ";
    }
    for(int i = odp.size() - 1; i >= 0;--i){
        cout<<odp[i] <<" ";
    } 
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 388 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 600 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 464 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 464 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 396 KB Output is correct
63 Correct 0 ms 604 KB Output is correct
64 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 464 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #3
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 388 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 600 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 464 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 464 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 396 KB Output is correct
63 Correct 0 ms 604 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 344 KB Output is correct
66 Correct 0 ms 344 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 0 ms 344 KB Output is correct
75 Correct 0 ms 348 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 0 ms 348 KB Output is correct
78 Correct 0 ms 348 KB Output is correct
79 Correct 1 ms 344 KB Output is correct
80 Correct 1 ms 344 KB Output is correct
81 Correct 1 ms 468 KB Output is correct
82 Correct 1 ms 348 KB Output is correct
83 Correct 1 ms 348 KB Output is correct
84 Correct 1 ms 344 KB Output is correct
85 Correct 1 ms 352 KB Output is correct
86 Correct 1 ms 344 KB Output is correct
87 Correct 1 ms 464 KB Output is correct
88 Correct 1 ms 344 KB Output is correct
89 Partially correct 3 ms 348 KB Failed to provide a successful strategy.
90 Correct 2 ms 348 KB Output is correct
91 Correct 2 ms 344 KB Output is correct
92 Correct 2 ms 344 KB Output is correct
93 Correct 3 ms 344 KB Output is correct
94 Correct 2 ms 344 KB Output is correct
95 Partially correct 3 ms 348 KB Failed to provide a successful strategy.
96 Partially correct 3 ms 348 KB Failed to provide a successful strategy.
97 Correct 2 ms 348 KB Output is correct
98 Correct 2 ms 348 KB Output is correct
99 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
100 Correct 2 ms 348 KB Output is correct
101 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
102 Correct 2 ms 348 KB Output is correct
103 Partially correct 2 ms 516 KB Failed to provide a successful strategy.
104 Partially correct 2 ms 344 KB Failed to provide a successful strategy.
105 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
106 Correct 2 ms 348 KB Output is correct
107 Correct 2 ms 512 KB Output is correct
108 Correct 3 ms 348 KB Output is correct
109 Correct 2 ms 348 KB Output is correct
110 Correct 2 ms 348 KB Output is correct
111 Partially correct 2 ms 344 KB Failed to provide a successful strategy.
112 Correct 2 ms 348 KB Output is correct
113 Partially correct 3 ms 348 KB Failed to provide a successful strategy.
114 Correct 2 ms 344 KB Output is correct
115 Correct 2 ms 348 KB Output is correct
116 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
117 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
118 Partially correct 3 ms 348 KB Failed to provide a successful strategy.
119 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
120 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
121 Correct 2 ms 344 KB Output is correct
122 Correct 2 ms 648 KB Output is correct
123 Correct 2 ms 348 KB Output is correct
124 Correct 2 ms 344 KB Output is correct
125 Correct 2 ms 348 KB Output is correct
126 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
127 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
128 Partially correct 2 ms 348 KB Failed to provide a successful strategy.
129 Correct 1 ms 344 KB Output is correct
130 Correct 1 ms 348 KB Output is correct
131 Correct 1 ms 348 KB Output is correct
132 Correct 1 ms 348 KB Output is correct
133 Correct 1 ms 348 KB Output is correct
134 Correct 0 ms 348 KB Output is correct
135 Correct 0 ms 348 KB Output is correct
136 Correct 0 ms 348 KB Output is correct
137 Correct 0 ms 348 KB Output is correct
138 Correct 1 ms 348 KB Output is correct
139 Correct 0 ms 344 KB Output is correct
140 Correct 0 ms 348 KB Output is correct
141 Correct 0 ms 348 KB Output is correct
142 Correct 0 ms 348 KB Output is correct
143 Correct 0 ms 344 KB Output is correct
144 Correct 1 ms 348 KB Output is correct
145 Correct 1 ms 344 KB Output is correct