답안 #830140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830140	2023-08-18T19:58:32 Z	MohamedAhmed04	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1794 ms	52716 KB

designated_cities

#include <bits/stdc++.h>
 
using namespace std ;
 
const int MAX = 2e5 + 10 ;
 
int arr[MAX] ;
int n , q ;
 
vector< vector< pair<int , int> > >adj(MAX) ;
 
long long ans[MAX] ;
 
int mark[MAX] ;
int sz[MAX] ;
int cursrc , cursz ;
long long curcost ;
 
pair<long long , int>tree[4 * MAX] ;
long long lazy[4 * MAX] ;

int id[MAX] ;
long long val3[MAX] ;
 
void build(int node , int l , int r)
{
	lazy[node] = 0 ;
	if(l == r)
	{
		tree[node] = {val3[id[l]] , id[l]} ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(node << 1 , l , mid) ;
	build(node << 1 | 1 , mid+1 , r) ;
	tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
 
void prop(int node , int l , int r)
{
	tree[node].first += lazy[node] ;
	if(l != r)
	{
		lazy[node << 1] += lazy[node] ;
		lazy[node << 1 | 1] += lazy[node] ;
	}
	lazy[node] = 0 ;
}
 
void update(int node , int l , int r , int from , int to , int val)
{
	if(lazy[node])
		prop(node , l , r) ;
	if(from > r || to < l)
		return ;
	if(l >= from && r <= to)
	{
		tree[node].first += val ;
		if(l != r)
			lazy[node << 1] += val , lazy[node << 1 | 1] += val ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , from , to , val) ;
	update(node << 1 | 1 , mid+1 , r , from , to , val) ;
	tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
}
 
pair<long long , int>query(int node , int l , int r , int from , int to)
{
	if(lazy[node])
		prop(node , l , r) ;
	if(from > r || to < l || from > to)
		return {-1e18 , -1e9} ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	pair<long long , int>a = query(node << 1 , l , mid , from , to) ;
	pair<long long , int>b = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return max(a , b) ;
}
 
void dfs_pre(int node , int par)
{
	sz[node] = 1 ;
	for(auto &childd : adj[node])
	{
		int child = childd.first ;
		if(child == par || mark[child])
			continue ;
		dfs_pre(child , node) ;
		sz[node] += sz[child] ;
	}
}
 
int FindCentroid(int node , int par)
{
	for(auto &childd : adj[node])
	{
		int child = childd.first ;
		if(child == par || mark[child])
			continue ;
		if(sz[child] > cursz / 2)
			return FindCentroid(child , node) ;
	}
	return node ;
}
 
int val[MAX] ;
int in[MAX] , out[MAX] ;
int tim = 0 ;
int sub[MAX] , P[MAX] , erased[MAX] , edgcost[MAX] ;
long long sum[MAX] , Max[MAX] ;
 
void dfs(int node , int par)
{
	in[node] = ++tim , id[tim] = node , P[node] = par ;
	curcost += val[node] , erased[node] = 0 ;
	sum[node] = Max[node] = val[node] ;
	for(auto &childd : adj[node])
	{
		int child = childd.first , w = childd.second ;
		if(child == par)
			edgcost[node] = w ;
		if(child == par || mark[child])
			continue ;
		val[child] = w , val3[child] = val3[node] + w ;
		if(in[node] == 1) //centroid
			sub[child] = child ;
		else
			sub[child] = sub[node] ;
		dfs(child , node) ;
		sum[node] += sum[child] ;
		Max[node] = max(Max[node] , Max[child] + val[node]) ;
	}
	out[node] = tim ;
}
 
void Erase(int node)
{
	while((!erased[node]) && node)
	{
		erased[node] = 1 ;
		update(1 , 1 , cursz , in[node] , out[node] , -1 * val[node]) ;
		node = P[node] ;
	}
}
 
void solve(int src , long long cost)
{
	tim = 0 ;
	cursrc = src , curcost = cost ;
	dfs_pre(src , 0) ;
	cursz = sz[src] ;
	int centroid = FindCentroid(src , -1) ;
	val[centroid] = val3[centroid] = 0 ;
	dfs(centroid , 0) ;
	build(1 , 1 , cursz) ;
	ans[1] = min(ans[1] , curcost) ;
	long long Max1 = 0 , Max2 = 0 ;
	for(auto &childd : adj[centroid])
	{
		int child = childd.first , w = childd.second ;
		if(mark[child])
			continue ;
		if(Max[child] > Max1)
			Max2 = Max1 , Max1 = Max[child] ;
		else if(Max[child] > Max2)
			Max2 = Max[child] ;
	}
	bool flag = true ;
	int prv ;
	for(int i = 1 ; i <= cursz ; ++i)
	{
		pair<long long , int>p = query(1 , 1 , cursz , 1 , cursz) ;
		if((!p.first))
		{
			ans[i] = min({ans[i] , curcost , ans[i-1]}) ;
			break ;
		}
		int node = p.second ;
		if(i > 1)
			flag &= (sub[node] == sub[prv]) ;
		curcost -= p.first , Erase(node) ;
		if(!flag)
			ans[i] = min(ans[i] , curcost) ;
		else if(i > 1)
			ans[i] = min(ans[i] , curcost + p.first - Max2) ;
		prv = node ;
	}
	mark[centroid] = 1 ;
	for(auto &childd : adj[centroid])
	{
		int child = childd.first , w = childd.second ;
		if(mark[child])
			continue ;
		solve(child , cost + sum[centroid] - sum[child] + edgcost[child]) ;
	}
}
 
int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y , c , d ;
		cin>>x>>y>>c>>d ;
		adj[x].emplace_back(y , c) ;
		adj[y].emplace_back(x , d) ;
	}
	for(int i = 0 ; i <= n ; ++i)
		ans[i] = 1e18 ;
	solve(1 , 0) ;
	for(int i = 1 ; i <= n ; ++i)
		ans[i] = min(ans[i] , ans[i-1]) ;
	cin>>q ;
	while(q--)
	{
		int x ;
		cin>>x ;
		cout<<ans[x]<<"\n" ;
	} 
	return 0 ;
}	

Compilation message

designated_cities.cpp: In function 'void solve(int, long long int)':
designated_cities.cpp:163:30: warning: unused variable 'w' [-Wunused-variable]
  163 |   int child = childd.first , w = childd.second ;
      |                              ^
designated_cities.cpp:194:30: warning: unused variable 'w' [-Wunused-variable]
  194 |   int child = childd.first , w = childd.second ;
      |                              ^

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	2 ms	5076 KB	Output is correct
3	Correct	2 ms	5076 KB	Output is correct
4	Correct	2 ms	5076 KB	Output is correct
5	Correct	2 ms	5076 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	2 ms	5076 KB	Output is correct
8	Correct	2 ms	5076 KB	Output is correct
9	Correct	2 ms	5076 KB	Output is correct
10	Correct	2 ms	5076 KB	Output is correct
11	Correct	2 ms	5076 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	5076 KB	Output is correct
2	Correct	1066 ms	38684 KB	Output is correct
3	Correct	1376 ms	50360 KB	Output is correct
4	Correct	1100 ms	38860 KB	Output is correct
5	Correct	336 ms	38712 KB	Output is correct
6	Correct	1427 ms	40364 KB	Output is correct
7	Correct	334 ms	38792 KB	Output is correct
8	Correct	1513 ms	50792 KB	Output is correct
9	Correct	237 ms	39184 KB	Output is correct

Subtask #3

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	1123 ms	38640 KB	Output is correct
3	Correct	1440 ms	52556 KB	Output is correct
4	Correct	1078 ms	38620 KB	Output is correct
5	Correct	355 ms	38692 KB	Output is correct
6	Correct	1400 ms	40876 KB	Output is correct
7	Correct	247 ms	39080 KB	Output is correct
8	Correct	1573 ms	46548 KB	Output is correct
9	Correct	232 ms	39256 KB	Output is correct

Subtask #4

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	2 ms	5076 KB	Output is correct
3	Correct	2 ms	5076 KB	Output is correct
4	Correct	2 ms	5076 KB	Output is correct
5	Correct	2 ms	5076 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	2 ms	5076 KB	Output is correct
8	Correct	2 ms	5076 KB	Output is correct
9	Correct	2 ms	5076 KB	Output is correct
10	Correct	2 ms	5076 KB	Output is correct
11	Correct	2 ms	5076 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	6 ms	5440 KB	Output is correct
14	Correct	6 ms	5520 KB	Output is correct
15	Correct	6 ms	5460 KB	Output is correct
16	Correct	6 ms	5432 KB	Output is correct
17	Correct	6 ms	5332 KB	Output is correct
18	Correct	8 ms	5568 KB	Output is correct
19	Correct	6 ms	5332 KB	Output is correct
20	Correct	4 ms	5460 KB	Output is correct
21	Correct	7 ms	5460 KB	Output is correct
22	Correct	6 ms	5332 KB	Output is correct
23	Correct	6 ms	5332 KB	Output is correct
24	Correct	4 ms	5460 KB	Output is correct
25	Correct	7 ms	5460 KB	Output is correct
26	Correct	4 ms	5460 KB	Output is correct

Subtask #5

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	5076 KB	Output is correct
2	Correct	1066 ms	38684 KB	Output is correct
3	Correct	1376 ms	50360 KB	Output is correct
4	Correct	1100 ms	38860 KB	Output is correct
5	Correct	336 ms	38712 KB	Output is correct
6	Correct	1427 ms	40364 KB	Output is correct
7	Correct	334 ms	38792 KB	Output is correct
8	Correct	1513 ms	50792 KB	Output is correct
9	Correct	237 ms	39184 KB	Output is correct
10	Correct	3 ms	5076 KB	Output is correct
11	Correct	1123 ms	38640 KB	Output is correct
12	Correct	1440 ms	52556 KB	Output is correct
13	Correct	1078 ms	38620 KB	Output is correct
14	Correct	355 ms	38692 KB	Output is correct
15	Correct	1400 ms	40876 KB	Output is correct
16	Correct	247 ms	39080 KB	Output is correct
17	Correct	1573 ms	46548 KB	Output is correct
18	Correct	232 ms	39256 KB	Output is correct
19	Correct	3 ms	5076 KB	Output is correct
20	Correct	1038 ms	38696 KB	Output is correct
21	Correct	1381 ms	52716 KB	Output is correct
22	Correct	1060 ms	38636 KB	Output is correct
23	Correct	1149 ms	38668 KB	Output is correct
24	Correct	1148 ms	38912 KB	Output is correct
25	Correct	1085 ms	38772 KB	Output is correct
26	Correct	1069 ms	38784 KB	Output is correct
27	Correct	329 ms	38768 KB	Output is correct
28	Correct	1371 ms	40412 KB	Output is correct
29	Correct	992 ms	38700 KB	Output is correct
30	Correct	946 ms	38860 KB	Output is correct
31	Correct	273 ms	38876 KB	Output is correct
32	Correct	1535 ms	47056 KB	Output is correct
33	Correct	239 ms	39148 KB	Output is correct

Subtask #6

44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	2 ms	5076 KB	Output is correct
3	Correct	2 ms	5076 KB	Output is correct
4	Correct	2 ms	5076 KB	Output is correct
5	Correct	2 ms	5076 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	2 ms	5076 KB	Output is correct
8	Correct	2 ms	5076 KB	Output is correct
9	Correct	2 ms	5076 KB	Output is correct
10	Correct	2 ms	5076 KB	Output is correct
11	Correct	2 ms	5076 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	1066 ms	38684 KB	Output is correct
14	Correct	1376 ms	50360 KB	Output is correct
15	Correct	1100 ms	38860 KB	Output is correct
16	Correct	336 ms	38712 KB	Output is correct
17	Correct	1427 ms	40364 KB	Output is correct
18	Correct	334 ms	38792 KB	Output is correct
19	Correct	1513 ms	50792 KB	Output is correct
20	Correct	237 ms	39184 KB	Output is correct
21	Correct	3 ms	5076 KB	Output is correct
22	Correct	1123 ms	38640 KB	Output is correct
23	Correct	1440 ms	52556 KB	Output is correct
24	Correct	1078 ms	38620 KB	Output is correct
25	Correct	355 ms	38692 KB	Output is correct
26	Correct	1400 ms	40876 KB	Output is correct
27	Correct	247 ms	39080 KB	Output is correct
28	Correct	1573 ms	46548 KB	Output is correct
29	Correct	232 ms	39256 KB	Output is correct
30	Correct	2 ms	5076 KB	Output is correct
31	Correct	6 ms	5440 KB	Output is correct
32	Correct	6 ms	5520 KB	Output is correct
33	Correct	6 ms	5460 KB	Output is correct
34	Correct	6 ms	5432 KB	Output is correct
35	Correct	6 ms	5332 KB	Output is correct
36	Correct	8 ms	5568 KB	Output is correct
37	Correct	6 ms	5332 KB	Output is correct
38	Correct	4 ms	5460 KB	Output is correct
39	Correct	7 ms	5460 KB	Output is correct
40	Correct	6 ms	5332 KB	Output is correct
41	Correct	6 ms	5332 KB	Output is correct
42	Correct	4 ms	5460 KB	Output is correct
43	Correct	7 ms	5460 KB	Output is correct
44	Correct	4 ms	5460 KB	Output is correct
45	Correct	3 ms	5076 KB	Output is correct
46	Correct	1038 ms	38696 KB	Output is correct
47	Correct	1381 ms	52716 KB	Output is correct
48	Correct	1060 ms	38636 KB	Output is correct
49	Correct	1149 ms	38668 KB	Output is correct
50	Correct	1148 ms	38912 KB	Output is correct
51	Correct	1085 ms	38772 KB	Output is correct
52	Correct	1069 ms	38784 KB	Output is correct
53	Correct	329 ms	38768 KB	Output is correct
54	Correct	1371 ms	40412 KB	Output is correct
55	Correct	992 ms	38700 KB	Output is correct
56	Correct	946 ms	38860 KB	Output is correct
57	Correct	273 ms	38876 KB	Output is correct
58	Correct	1535 ms	47056 KB	Output is correct
59	Correct	239 ms	39148 KB	Output is correct
60	Correct	2 ms	5076 KB	Output is correct
61	Correct	1158 ms	40232 KB	Output is correct
62	Correct	1375 ms	50864 KB	Output is correct
63	Correct	1091 ms	40172 KB	Output is correct
64	Correct	1032 ms	40192 KB	Output is correct
65	Correct	1070 ms	39936 KB	Output is correct
66	Correct	1083 ms	40056 KB	Output is correct
67	Correct	1127 ms	39940 KB	Output is correct
68	Correct	409 ms	40124 KB	Output is correct
69	Correct	1385 ms	41596 KB	Output is correct
70	Correct	1344 ms	39976 KB	Output is correct
71	Correct	997 ms	40260 KB	Output is correct
72	Correct	364 ms	40864 KB	Output is correct
73	Correct	1794 ms	46888 KB	Output is correct
74	Correct	271 ms	42084 KB	Output is correct