Submission #1092658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092658		Sunbae	Capital City (JOI20_capital_city)	C++17	0 / 100	927 ms	524288 KiB

capital_city

#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 2e5 + 5;
set<int> H[N], s;
vector<int> g[N];
int sz[N], ded[N], have[N], fq[N], c[N], ct;
int fsz(int u, int p){ sz[u] = 1; for(int v: g[u]) if(!ded[v] && v != p) sz[u] += fsz(v, u); return sz[u];}
int fcen(int u, int p, int tsz){ for(int v: g[u]) if(!ded[v] && v != p && (sz[v]<<1) > tsz) return fcen(v, u, tsz); return u;}

void dfs(int u, int p){
	++have[c[u]];
	for(int v: g[u]) if(!ded[v] && v != p) dfs(v, u);
}
void efs(int u, int p){
	--have[c[u]];
	for(int v: g[u]) if(!ded[v] && v != p) efs(v, u); 
}
void ffs(int u, int p){
	++fq[c[u]]; s.insert(c[u]);
	if(have[c[u]]){
		//if(s.size() > H[c[u]].size()) swap(s, H[c[u]]);
		H[c[u]].insert(s.begin(), s.end());
		H[c[u]].insert(c[ct]);
	}
	for(int v: g[u]) if(!ded[v] && v != p) ffs(v, u);
	if(!--fq[c[u]]) s.erase(c[u]);
}

void cd(int u){
	ded[ct = u = fcen(u, -1, fsz(u, -1))] = 1;
	dfs(u, u);
	for(int v: g[u]) if(!ded[v]){ efs(v, u); s.clear(); ffs(v, u); dfs(v, u);}
	efs(u, u);
	for(int v: g[u]) if(!ded[v]) cd(v);
}
signed main(){
	int n, k; scanf("%d %d", &n, &k);
	for(int i = 0, u, v; i<n-1; ++i){
		scanf("%d %d", &u, &v); --u; --v;
		g[u].push_back(v); g[v].push_back(u);
	}
	for(int i = 0; i<n; ++i){ scanf("%d", c+i); --c[i];}
	cd(0);
	int mn = k;
	for(int i = 0; i<k; ++i){
		for(int x: H[i]) printf("%d ", x+1); puts("");
	}
	z;
	for(int i = 0; i<k; ++i) mn = min(mn, (int)H[i].size() - 1);
	printf("%d", mn);
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:47:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   47 |   for(int x: H[i]) printf("%d ", x+1); puts("");
      |   ^~~
capital_city.cpp:47:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   47 |   for(int x: H[i]) printf("%d ", x+1); puts("");
      |                                        ^~~~
capital_city.cpp:38:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  int n, k; scanf("%d %d", &n, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d %d", &u, &v); --u; --v;
      |   ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:43:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  for(int i = 0; i<n; ++i){ scanf("%d", c+i); --c[i];}
      |                            ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59