Submission #106558

#	Time	Username	Problem	Language	Result	Execution time	Memory
106558		zbww	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1320 ms	35292 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
const int N = 200001;
const long long inf = 1000000000000000ll;
struct edge{
	int to,nxt;
	long long w;
}tree[N << 1];
int n,q,head[N],cnt = 0;
void addedge(int u,int v,long long w){
	edge x = {v,head[u],w};
	tree[head[u] = cnt++] = x;
}
template<class T>
void read(T &x){
	int sgn = 1;
	char ch;
	x = 0;
	for(ch = getchar();(ch < '0' || ch > '9') && ch != '-';ch = getchar());
	if(ch == '-')ch = getchar(),sgn = -1;
	for(;'0' <= ch && ch <= '9';ch = getchar())x = x * 10 + ch - '0';
	x *= sgn;
}
template<class T>
void write(T x){
	if(x < 0)putchar('-'),write(-x);
	else if(x < 10)putchar(x + '0');
	else write(x / 10),putchar(x % 10 + '0');
}
long long ans[N],depth[N],sz[N];
bool visited[N];
int size[N],child[N];
int find_centroid(int u,int fa,int total,int &weight,int &pos){
	int w = total - size[u];
	for(int i = head[u];i >= 0;i = tree[i].nxt){
		int v = tree[i].to;
		if(!visited[v] && v != fa){
			find_centroid(v,u,total,weight,pos);
			w = max(w,size[v]);
		}
	}
	if(w < weight)weight = w,pos = u;
}
void dfs1(int u,int edge){
	sz[u] = depth[u] = tree[edge ^ 1].w,child[u] = 0,size[u] = 1;
	for(int i = head[u];i >= 0;i = tree[i].nxt){
		int v = tree[i].to;
		if(!visited[v] && i != edge){
			dfs1(v,i ^ 1);
			size[u] += size[v],sz[u] += sz[v];
			if(!child[u] || depth[child[u]] < depth[v]){
				child[u] = v;
				depth[u] = tree[edge ^ 1].w + depth[child[u]];
			}
		}
	}
}
struct node{
	int belong;
	long long d;
	bool operator < (node other) const{
		return d > other.d;
	}
}chain[N];
int tot = 0;
void dfs2(int u,int fa,int root,int t){
	if(u == t){
		node x = {root,depth[u]};
		chain[++tot] = x;
	}
	if(child[u])dfs2(child[u],u,root,t);
	for(int i = head[u];i >= 0;i = tree[i].nxt){
		int v = tree[i].to;
		if(!visited[v] && v != fa && v != child[u])dfs2(v,u,root,v);
	}
}
void divide_and_conquer(int u,long long w){
	visited[u] = true,sz[u] = 0ll,size[u] = 1;
	node x = {u,0ll};
	chain[tot = 0] = x;
	for(int i = head[u];i >= 0;i = tree[i].nxt){
		int v = tree[i].to;
		if(!visited[v]){
			dfs1(v,i ^ 1);
			sz[u] += sz[v],size[u] += size[v];
			dfs2(v,u,v,v);
		}
	}
	sort(chain,chain + tot + 1);
	int p = 0;
	for(int i = 1;i <= tot;i++){
		if(chain[i].belong != chain[0].belong){
			p = i;
			break;
		}
	}
	long long total = 0ll;
	ans[1] = min(ans[1],sz[u] + w);
	for(int i = 0;i < p;i++){
		if(i >= 0)total += chain[i].d;
		ans[i + 2] = min(ans[i + 2],sz[u] - total - chain[p].d + w);
	}
	for(int i = p;i <= tot;i++){
		total += chain[i].d;
		ans[i + 1] = min(ans[i + 1],sz[u] - total + w);
	}
	for(int i = tot + 2;i <= size[u];i++)ans[i] = min(ans[i],sz[u] - total + w);
	for(int i = head[u];i >= 0;i = tree[i].nxt){
		int v = tree[i].to;
		if(!visited[v]){
			int weight = n,pos = v;
			find_centroid(v,u,size[v],weight,pos);
			divide_and_conquer(pos,w + sz[u] - sz[v] + tree[i ^ 1].w);
		}
	}
	visited[u] = false;
}
int main(){
	read(n);
	for(int i = 1;i <= n;i++)head[i] = -1;
	for(int i = 1;i < n;i++){
		int u,v;
		long long w1,w2;
		read(u),read(v);
		read(w1),read(w2);
		addedge(u,v,w1);
		addedge(v,u,w2);
	}
	for(int i = 1;i <= n;i++)ans[i] = inf;
	divide_and_conquer(1,0ll);
	read(q);
	for(int i = 1;i <= q;i++){
		int x;
		read(x);
		write(ans[x]),putchar('\n');
	}
	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int find_centroid(int, int, int, int&, int&)':
designated_cities.cpp:43:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44