oj.uz

답안 #652497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652497 2022-10-22T18:32:55 Z kinope Newspapers (CEOI21_newspapers) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<int> in, ojc, ojc2, d, nr, gle;

void Resize(int n){
		g.resize(n+1); gle.resize(n+1);
		in.resize(n+1); nr.resize(n+1);
		ojc.resize(n+1); ojc2.resize(n+1);
		d.resize(n+1);
}

void dfs(int x, int o, int odl){
		for(int u : g[x]) if(u != o) dfs(u, x, odl + 1);
		ojc[x] = o; d[x] = odl;
}

void dfsG(int x, int o){
		for(int u : g[x]) if(u != o){
				dfsG(u, x);
				gle[x] = max(gle[x], gle[u]);}
		++gle[x];
}

int main(){
		
		int n, m, a, b;
		scanf("%d%d", &n, &m);
		if(m != n-1){ printf("NO"); return 0; }
		Resize(n);
		
		for(int i = n; --i; ){
				scanf("%d%d", &a, &b);
				g[a].emplace_back(b);
				g[b].emplace_back(a);
				++in[a], ++in[b];
		}
		int X, Y, odl = 0;
		dfs(1, 0, 0);
		for(int i = 1; i <= n; ++i) if(d[i] > odl) X = i, odl = d[i];
		dfs(X, 0, 0);
		odl = 0;
		for(int i = 1; i <= n; ++i) if(d[i] > odl) Y = i, odl = d[i];
		dfsG(Y, 0);
		vector<int> ans;
		
		for(int x = Y; x; x = ojc[x]){
				ojc2[ojc[x]] = x;
				if(x == X || x == Y) continue;
				ans.emplace_back(x);
				for(int u : g[x]) if(u != ojc[x] && u != ojc2[x]){
						if(gle[u] > 2) { printf("NO"); return 0; }
						else if(gle[u] == 1) continue;
						ans.emplace_back(u);
						ans.emplace_back(x);
				}
				
		}
		
		for(int x = X; x; x = ojc2[x]){
				if(x == X || x == Y) continue;
				ans.emplace_back(x);
				for(int u : g[x]) if(u != ojc[x] && u != ojc2[x]){
						if(gle[u] == 1) continue;
						ans.emplace_back(u);
						ans.emplace_back(x);
				}
				//printf("%d ", x);
		}
		
		printf("YES\n%d\n", (int) ans.size());
		for(int u : ans) printf("%d ", u);
		
		return 0;
}

Compilation message

newspapers.cpp: In function 'int main()':
newspapers.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
newspapers.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d%d", &a, &b);
      |     ~~~~~^~~~~~~~~~~~~~~~
newspapers.cpp:63:15: warning: 'Y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     if(x == X || x == Y) continue;
      |        ~~~~~~~^~~~~~~~~
newspapers.cpp:62:11: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |   for(int x = X; x; x = ojc2[x]){
      |           ^

Subtask #1
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -