# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
934087 | 2024-02-26T19:02:00 Z | sysia | Newspapers (CEOI21_newspapers) | C++17 | 1 ms | 624 KB |
//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; void solve(){ int n, m; cin >> n >> m; if (m >= n){ cout << "NO\n"; return; } if (n == 1){ cout << "YES\n1\n1\n"; return; } vector<vector<int>>g(n+1); for (int i = 1; i<n; i++){ int a, b; cin >> a >> b; g[a].emplace_back(b); g[b].emplace_back(a); } vector<int>depth(n+1), par(n+1); function<void(int, int, int)>dfs = [&](int v, int pa, int pa2=-1){ par[v] = pa; for (auto x: g[v]){ if (x == pa || x == pa2) continue; depth[x] = depth[v]+1; dfs(x, v, -1); } }; dfs(1, 1, -1); T now = {-oo, -oo}; for (int v = 1; v <= n; v++) now = max(now, T{depth[v], v}); int L = now.second; depth[L] = 0; dfs(L, L, -1); now = {-oo, -oo}; for (int v = 1; v <= n; v++) now = max(now, T{depth[v], v}); int R = now.second; vector<int>curr; int u = R; while (1){ curr.emplace_back(u); if (u == L) break; u = par[u]; } reverse(curr.begin(), curr.end()); debug(curr); int s = (int)curr.size(); for (int rep = 0; rep < s; rep++){ int v = curr[rep]; depth[v] = 0; dfs(v, (rep ? curr[rep-1] : -1), (rep+1<s ? curr[rep+1] : -1)); } debug(depth); if (*max_element(depth.begin(), depth.end()) > 2) { cout << "NO\n"; return; } //fajna struktura drzewa miau cout << "YES\n"; //teraz wypisac strategie depth[L] = 0; dfs(L, L, -1); for (int v = 1; v <= n; v++) depth[v] %= 2; debug(depth); //depth mod 2 to kolory //1) Bob znajdowal sie w kolorze 0 na poczatku vector<int>ret; auto solve = [&](int v, int left, int right, int turn){ debug(v, left, right); if (depth[v] == turn) ret.emplace_back(v); for (auto x: g[v]){ //teraz czarny kolor if (x == left || x == right || (int)g[x].size() == 1) continue; ret.emplace_back(x); ret.emplace_back(v); } }; for (int rep = 0; rep < s; rep++){ int v = curr[rep]; int turn = ((int)ret.size() % 2); solve(v, (rep ? curr[rep-1] : -1), (rep+1<s ? curr[rep+1] : -1), turn); } debug(ret); if ((int)ret.size()&1) ret.emplace_back(1); //jesli x nieparzysty, to znaczy ze jest inna kolejka niz if (s > 3){ for (int rep = 1; rep < s; rep++){ int v = curr[rep]; int turn = ((int)ret.size() % 2)^1; solve(v, (rep > 1 ? curr[rep-1] : -1), (rep+1<s ? curr[rep+1] : -1), turn); } } else { ret.emplace_back(curr[1]); } cout << (int)ret.size() << "\n"; for (auto xx: ret) cout << xx << " "; cout << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 600 KB | Output is correct |
2 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
3 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
4 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
5 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
6 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
11 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
12 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
13 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
14 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
15 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
16 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
17 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
18 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
19 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
20 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
21 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
22 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
23 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
24 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
25 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
26 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
27 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
28 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
31 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
32 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
33 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
34 | Correct | 0 ms | 348 KB | Output is correct |
35 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
36 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
37 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
38 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
39 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
40 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
41 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
42 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
43 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
44 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
45 | Correct | 0 ms | 348 KB | Output is correct |
46 | Correct | 0 ms | 348 KB | Output is correct |
47 | Correct | 0 ms | 348 KB | Output is correct |
48 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
49 | Correct | 0 ms | 348 KB | Output is correct |
50 | Correct | 0 ms | 348 KB | Output is correct |
51 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
52 | Correct | 0 ms | 348 KB | Output is correct |
53 | Correct | 0 ms | 348 KB | Output is correct |
54 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
55 | Correct | 0 ms | 348 KB | Output is correct |
56 | Correct | 0 ms | 348 KB | Output is correct |
57 | Correct | 1 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 | 348 KB | Output is correct |
63 | Correct | 0 ms | 348 KB | Output is correct |
64 | Correct | 0 ms | 348 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
3 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
4 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
5 | Partially correct | 0 ms | 600 KB | Provide a successful but not optimal strategy. |
6 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
7 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
8 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
9 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
10 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
11 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
12 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
13 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
14 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
15 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
16 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
17 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
18 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
19 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
20 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 600 KB | Output is correct |
2 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
3 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
4 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
5 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
6 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
7 | Correct | 1 ms | 348 KB | Output is correct |
8 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
11 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
12 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
13 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
14 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
15 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
16 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
17 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
18 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
19 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
20 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
21 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
22 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
23 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
24 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
25 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
26 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
27 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
28 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
29 | Correct | 0 ms | 348 KB | Output is correct |
30 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
31 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
32 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
33 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
34 | Correct | 0 ms | 348 KB | Output is correct |
35 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
36 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
37 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
38 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
39 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
40 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
41 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
42 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
43 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
44 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
45 | Correct | 0 ms | 348 KB | Output is correct |
46 | Correct | 0 ms | 348 KB | Output is correct |
47 | Correct | 0 ms | 348 KB | Output is correct |
48 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
49 | Correct | 0 ms | 348 KB | Output is correct |
50 | Correct | 0 ms | 348 KB | Output is correct |
51 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
52 | Correct | 0 ms | 348 KB | Output is correct |
53 | Correct | 0 ms | 348 KB | Output is correct |
54 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
55 | Correct | 0 ms | 348 KB | Output is correct |
56 | Correct | 0 ms | 348 KB | Output is correct |
57 | Correct | 1 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 | 348 KB | Output is correct |
63 | Correct | 0 ms | 348 KB | Output is correct |
64 | Correct | 0 ms | 348 KB | Output is correct |
65 | Correct | 0 ms | 348 KB | Output is correct |
66 | Partially correct | 0 ms | 404 KB | Provide a successful but not optimal strategy. |
67 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
68 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
69 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
70 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
71 | Correct | 0 ms | 348 KB | Output is correct |
72 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
73 | Correct | 0 ms | 348 KB | Output is correct |
74 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
75 | Partially correct | 1 ms | 344 KB | Provide a successful but not optimal strategy. |
76 | Partially correct | 0 ms | 344 KB | Provide a successful but not optimal strategy. |
77 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
78 | Partially correct | 0 ms | 348 KB | Provide a successful but not optimal strategy. |
79 | Correct | 0 ms | 348 KB | Output is correct |
80 | Correct | 0 ms | 348 KB | Output is correct |
81 | Correct | 1 ms | 348 KB | Output is correct |
82 | Correct | 1 ms | 348 KB | Output is correct |
83 | Correct | 1 ms | 344 KB | Output is correct |
84 | Correct | 1 ms | 344 KB | Output is correct |
85 | Correct | 1 ms | 348 KB | Output is correct |
86 | Correct | 1 ms | 348 KB | Output is correct |
87 | Correct | 1 ms | 348 KB | Output is correct |
88 | Correct | 0 ms | 348 KB | Output is correct |
89 | Partially correct | 1 ms | 624 KB | Provide a successful but not optimal strategy. |
90 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
91 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
92 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
93 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
94 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
95 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
96 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
97 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
98 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
99 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
100 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
101 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
102 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
103 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
104 | Partially correct | 1 ms | 348 KB | Provide a successful but not optimal strategy. |
105 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
106 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
107 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
108 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
109 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
110 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
111 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
112 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
113 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
114 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
115 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
116 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
117 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
118 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
119 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
120 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
121 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
122 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
123 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
124 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
125 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
126 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
127 | Partially correct | 1 ms | 344 KB | Provide a successful but not optimal strategy. |
128 | Partially correct | 1 ms | 600 KB | Provide a successful but not optimal strategy. |
129 | Correct | 1 ms | 348 KB | Output is correct |
130 | Correct | 1 ms | 348 KB | Output is correct |
131 | Correct | 0 ms | 348 KB | Output is correct |
132 | Correct | 1 ms | 348 KB | Output is correct |
133 | Correct | 0 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 | 0 ms | 344 KB | Output is correct |
139 | Correct | 1 ms | 348 KB | Output is correct |
140 | Correct | 1 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 | 1 ms | 344 KB | Output is correct |
144 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |
145 | Partially correct | 1 ms | 604 KB | Provide a successful but not optimal strategy. |