답안 #1010201

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010201 2024-06-28T13:07:50 Z PoPularPlusPlus Meetings 2 (JOI21_meetings2) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 200004;
vector<int> adj[N];
int siz[N];
bool vis[N];
int ans[N];
int mx[N];

void cal_siz(int node , int par){
	siz[node] = 1;
	for(int i : adj[node]){
		if(i!=par && !vis[i]){
			cal_siz(i , node);
			siz[node] += siz[i];
		}
	}
}

int centroid(int node , int par , int tot){
	for(int i : adj[node]){
		if(!vis[i] && i != par && siz[i] >= tot){
			return centroid(i , node , tot);
		}
	}
	return node;
}

void dfs(int node , int par , int dis){
	mx[siz[node]] = max(mx[siz[node]] , dis);
	for(int i : adj[node]){
		if(i!=par && !vis[i])dfs(i , node , dis + 1);
	}
}

void centroid_decomposition(int node){
	cal_siz(node , node);
	int tot = siz[node];
	int root = centroid(node , node , (tot)/2);
	cal_siz(root,root);
	vector<pair<int,int>> v[tot + 2];
	int mx_siz = 0;
	for(int i : adj[root]){
		if(!vis[i]){
			mx_siz = max(mx_siz , siz[i]);
			for(int j = 0; j <= siz[i]; j++){
				mx[j] = -1;
			}
			dfs(i , root , 1);
			for(int j = 1; j <= siz[i]; j++){
				//cout << mx[j] << ' ';
				v[j].pb(mp(mx[j],i));
				sort(all(v[j]),greater<>());
				while(v[j].size() > 2)v[j].pop_back();
			}
			//cout << '\n';
		}
	}

	v[tot-mx_siz].pb(mp(0,-1));\
	sort(all(v[tot-mx_siz] , greater<>()));
	while(v[tot-mx_siz].size() > 2)v[tot-mx_siz].pop_back();

	/*for(int i = tot; i >= 0; i--){
		cout << i << '\n';
		for(auto j : v[tot]){
			cout << j.vf << ' ' << j.vs << '\n';
		}
	}*/

	for(int i = tot; i >= 0; i--){
		for(auto j : v[i + 1]){
			v[i].pb(j);
		}
		sort(all(v[i]),greater<>());
		if(v[i].size() >= 2){
			if(v[i][0].vs == v[i][1].vs){
				v[i].erase(v[i].begin() + 1);
			}
		}
		if(v[i].size() >= 2){
			if(v[i][0].vs == v[i][1].vs){
				v[i].erase(v[i].begin()+1);
			}
		}

		if(v[i].size() >= 2 && v[i][0].vs != v[i][1].vs){
			ans[2*i] = max(ans[2*i] , v[i][0].vf + v[i][1].vf + 1); 
		}
	}
	vis[root] = 1;
	for(int i : adj[root]){
		if(!vis[i]){
			centroid_decomposition(i);
		}
	}
}

void solve(){
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int a , b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	memset(vis,0,sizeof vis);
	memset(ans,-1,sizeof ans);

	centroid_decomposition(1);

	for(int i = n; i > 0; i--){
		if(i % 2 == 1){;}
		else {
			ans[i] = max(ans[i] , ans[i + 2]);
		}
	}
	for(int i = 1; i <= n; i++){
		if(i % 2 == 1)cout << 1 << '\n';
		else cout << ans[i] << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//int t;
	//cin >> t;
	//while(t--)
		solve();
}

Compilation message

meetings2.cpp:71:38: error: macro "all" passed 2 arguments, but takes just 1
   71 |  sort(all(v[tot-mx_siz] , greater<>()));
      |                                      ^
meetings2.cpp:6: note: macro "all" defined here
    6 | #define all(x) x.begin(),x.end()
      | 
meetings2.cpp: In function 'void centroid_decomposition(int)':
meetings2.cpp:71:7: error: 'all' was not declared in this scope; did you mean 'std::filesystem::perms::all'?
   71 |  sort(all(v[tot-mx_siz] , greater<>()));
      |       ^~~
      |       std::filesystem::perms::all
In file included from /usr/include/c++/10/filesystem:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from meetings2.cpp:1:
/usr/include/c++/10/bits/fs_fwd.h:148:7: note: 'std::filesystem::perms::all' declared here
  148 |       all  =  0777,
      |       ^~~