제출 #1067399

#제출 시각아이디문제언어결과실행 시간메모리
1067399AndreyNewspapers (CEOI21_newspapers)C++14
0 / 100
1 ms600 KiB
#include<bits/stdc++.h> using namespace std; vector<int> haha[10000]; vector<int> wow(0); vector<int> wut(0); int n,m; void dfs(int a, int t, int d) { if(d%2) { wow.push_back(a); } else { wut.push_back(a); } for(int v: haha[a]) { if(v != t) { dfs(v,a,d+1); } } } bool check() { vector<int> br(n+1); vector<int> br1(n+1); for(int i = 1; i <= n; i++) { br[i] = haha[i].size(); } for(int a: wow) { if(haha[a].size() == 1) { br[haha[a][0]]--; br[a] = -1; } } for(int i = 1; i <= n; i++) { br1[i] = br[i]; } for(int i = 1; i <= n; i++) { if(br1[i] == 1) { for(int v: haha[i]) { br[v]--; } br[i] = -1; } } for(int i = 1; i <= n; i++) { if(br[i] > 2) { return false; } } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; int a,b; for(int i = 0; i < m; i++) { cin >> a >> b; haha[a].push_back(b); haha[b].push_back(a); } if(m > n-1) { cout << "NO" << endl; return 0; } dfs(1,-1,0); if(check()) { cout << "YES" << endl; } else { swap(wow,wut); if(check()) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...