제출 #113060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113060		gs14004	Unique Cities (JOI19_ho_t5)	C++17	4 / 100	2057 ms	22120 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
using pi = pair<int, int>;

vector<int> gph[MAXN];
int n, m, r[2], dist[2][MAXN];
int a[MAXN], dp[MAXN];

void dfs_far(int x, int p){
	dp[x] = 0;
	for(auto &i : gph[x]){
		if(i != p){
			dfs_far(i, x);
			dp[x] = max(dp[x], dp[i] + 1);
		}
	}
}

struct jaryoguzo{
	vector<int> v;
	int mark[MAXN];
	void push_back(int x){
		v.push_back(x);
	}
	void pop_back(){
		v.pop_back();
	}
	void mark_interval(int x, int d){
		for(int i=0; i<x && i<v.size(); i++){
			mark[v.size()-1-i] += d;
		}
	}
	int query(){
		vector<int> cnt(m + 1);
		for(int i=0; i<v.size(); i++){
			if(!mark[i]) cnt[v[i]]++;
		}
		int dap = 0;
		for(int i=1; i<=m; i++){
			if(cnt[i]) dap++;
		}
		return dap;
	}
}JG;

int ret[MAXN];

void dfs_calc(int x, int p){
	pi ret1(0, -1), ret2(0, -1);
	for(auto &i : gph[x]){
		if(i != p){
			auto nxt = pi(dp[i] + 1, i);
			if(ret1 < nxt){
				ret2 = max(ret2, ret1);
				ret1 = nxt;
			}
			else if(ret2 < nxt){
				ret2 = nxt;
			}
		}
	}
	JG.mark_interval(ret1.first, +1);
	ret[x] = JG.query();
	JG.push_back(a[x]);
	for(auto &i : gph[x]){
		if(i == p) continue;
		if(i == ret1.second) continue;
		dfs_calc(i, x);
	}
	JG.pop_back();
	JG.mark_interval(ret1.first, -1);
	JG.mark_interval(ret2.first, +1);
	JG.push_back(a[x]);
	if(ret1.second != -1){
		dfs_calc(ret1.second, x);
	}
	JG.pop_back();
	JG.mark_interval(ret2.first, -1);
}

vector<int> solve(int r){
	dfs_far(r, -1);
	dfs_calc(r, -1);
	return vector<int>(ret + 1, ret + n + 1);
}

void fill_dist(int x, int p, int d, int l){
	dist[l][x] = d;
	for(auto &i : gph[x]){
		if(i != p){
			fill_dist(i, x, d + 1, l);
		}
	}
}

pi dfs(int x, int p){
	pi ret(0, x);
	for(auto &i : gph[x]){
		if(i != p){
			auto y = dfs(i, x);
			y.first++;
			ret = max(ret, y);
		}
	}
	return ret;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n-1; i++){
		int s, e; scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	for(int i=1; i<=n; i++) scanf("%d",&a[i]);
	r[0] = dfs(1, 0).second;
	r[1] = dfs(r[0], 0).second;
	fill_dist(r[0], -1, 0, 0);
	fill_dist(r[1], -1, 0, 1);
	auto v1 = solve(r[0]);
	auto v2 = solve(r[1]);
	for(int i=1; i<=n; i++){
		if(dist[0][i] <= dist[1][i]) printf("%d\n", v2[i-1]);
		else printf("%d\n", v1[i-1]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t5.cpp: In member function 'void jaryoguzo::mark_interval(int, int)':
joi2019_ho_t5.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<x && i<v.size(); i++){
                       ~^~~~~~~~~
joi2019_ho_t5.cpp: In member function 'int jaryoguzo::query()':
joi2019_ho_t5.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++){
                ~^~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:112:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, e; scanf("%d %d",&s,&e);
             ~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:116:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%d",&a[i]);
                          ~~~~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32