# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
532565 | 2022-03-03T08:15:52 Z | qwerasdfzxcl | Newspapers (CEOI21_newspapers) | C++14 | 1 ms | 460 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; constexpr int INF = 1e9; vector<int> adj[1010]; int dist[1010], n; pair<int, int> par[1010]; int _relax(int msk){ int ret = 0; for (int i=1;i<=n;i++) if (msk&(1<<(i-1))){ for (auto &v:adj[i]) ret |= (1<<(v-1)); } return ret; } int main(){ int m; scanf("%d %d", &n, &m); if (m>n-1) {printf("NO\n"); return 0;} for (int i=0;i<m;i++){ int x, y; scanf("%d %d", &x, &y); adj[x].push_back(y); adj[y].push_back(x); } int mx = (1<<n) - 1; fill(dist, dist+mx+1, INF); dist[mx] = 0; queue<int> q; q.push(mx); while(!q.empty()){ int s = q.front(); q.pop(); for (int i=0;i<n;i++){ int v = s & (mx ^ (1<<i)); v = _relax(v); if (dist[v]!=INF) continue; dist[v] = dist[s] + 1; par[v] = {s, i+1}; q.push(v); } } if (dist[0]==INF) printf("NO\n"); else{ printf("YES\n"); vector<int> ans; for (int cur = 0;cur!=mx;cur=par[cur].first) ans.push_back(par[cur].second); reverse(ans.begin(), ans.end()); printf("%d\n", (int)ans.size()); for (auto &x: ans) printf("%d ", x); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 320 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 320 KB | Output is correct |
9 | Runtime error | 1 ms | 460 KB | Execution killed with signal 11 |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 0 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Runtime error | 1 ms | 460 KB | Execution killed with signal 11 |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 320 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 320 KB | Output is correct |
9 | Runtime error | 1 ms | 460 KB | Execution killed with signal 11 |
10 | Halted | 0 ms | 0 KB | - |