Submission #830138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
830138	2023-08-18T19:54:49 Z	MohamedAhmed04	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1815 ms	58464 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)
{
	prop(node , l , r) ;
	if(from > r || to < l)
		return ;
	if(l >= from && r <= to)
	{
		lazy[node] += val ;
		prop(node , l , r) ;
		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)
{
	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:160:30: warning: unused variable 'w' [-Wunused-variable]
  160 |   int child = childd.first , w = childd.second ;
      |                              ^
designated_cities.cpp:191:30: warning: unused variable 'w' [-Wunused-variable]
  191 |   int child = childd.first , w = childd.second ;
      |                              ^

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 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	3 ms	5076 KB	Output is correct
5	Correct	2 ms	5076 KB	Output is correct
6	Correct	2 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	5 ms	5076 KB	Output is correct
10	Correct	2 ms	5076 KB	Output is correct
11	Correct	3 ms	5076 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5076 KB	Output is correct
2	Correct	1081 ms	38672 KB	Output is correct
3	Correct	1545 ms	50420 KB	Output is correct
4	Correct	1085 ms	38648 KB	Output is correct
5	Correct	343 ms	38596 KB	Output is correct
6	Correct	1452 ms	40436 KB	Output is correct
7	Correct	315 ms	38796 KB	Output is correct
8	Correct	1815 ms	50852 KB	Output is correct
9	Correct	267 ms	39264 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5036 KB	Output is correct
2	Correct	1172 ms	38668 KB	Output is correct
3	Correct	1514 ms	52636 KB	Output is correct
4	Correct	1132 ms	38732 KB	Output is correct
5	Correct	340 ms	38596 KB	Output is correct
6	Correct	1568 ms	40668 KB	Output is correct
7	Correct	260 ms	39044 KB	Output is correct
8	Correct	1615 ms	46472 KB	Output is correct
9	Correct	241 ms	39228 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 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	3 ms	5076 KB	Output is correct
5	Correct	2 ms	5076 KB	Output is correct
6	Correct	2 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	5 ms	5076 KB	Output is correct
10	Correct	2 ms	5076 KB	Output is correct
11	Correct	3 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	5460 KB	Output is correct
15	Correct	6 ms	5460 KB	Output is correct
16	Correct	7 ms	5332 KB	Output is correct
17	Correct	6 ms	5332 KB	Output is correct
18	Correct	6 ms	5332 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	5508 KB	Output is correct
22	Correct	6 ms	5448 KB	Output is correct
23	Correct	6 ms	5508 KB	Output is correct
24	Correct	4 ms	5508 KB	Output is correct
25	Correct	7 ms	5588 KB	Output is correct
26	Correct	4 ms	5460 KB	Output is correct

Subtask #5

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5076 KB	Output is correct
2	Correct	1081 ms	38672 KB	Output is correct
3	Correct	1545 ms	50420 KB	Output is correct
4	Correct	1085 ms	38648 KB	Output is correct
5	Correct	343 ms	38596 KB	Output is correct
6	Correct	1452 ms	40436 KB	Output is correct
7	Correct	315 ms	38796 KB	Output is correct
8	Correct	1815 ms	50852 KB	Output is correct
9	Correct	267 ms	39264 KB	Output is correct
10	Correct	2 ms	5036 KB	Output is correct
11	Correct	1172 ms	38668 KB	Output is correct
12	Correct	1514 ms	52636 KB	Output is correct
13	Correct	1132 ms	38732 KB	Output is correct
14	Correct	340 ms	38596 KB	Output is correct
15	Correct	1568 ms	40668 KB	Output is correct
16	Correct	260 ms	39044 KB	Output is correct
17	Correct	1615 ms	46472 KB	Output is correct
18	Correct	241 ms	39228 KB	Output is correct
19	Correct	2 ms	5076 KB	Output is correct
20	Correct	1202 ms	38816 KB	Output is correct
21	Correct	1495 ms	52600 KB	Output is correct
22	Correct	1096 ms	38740 KB	Output is correct
23	Correct	1153 ms	38740 KB	Output is correct
24	Correct	1183 ms	38680 KB	Output is correct
25	Correct	1127 ms	45172 KB	Output is correct
26	Correct	1159 ms	43984 KB	Output is correct
27	Correct	367 ms	45128 KB	Output is correct
28	Correct	1425 ms	46768 KB	Output is correct
29	Correct	1160 ms	45152 KB	Output is correct
30	Correct	1035 ms	44172 KB	Output is correct
31	Correct	299 ms	45340 KB	Output is correct
32	Correct	1736 ms	53444 KB	Output is correct
33	Correct	253 ms	45772 KB	Output is correct

Subtask #6

44.0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 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	3 ms	5076 KB	Output is correct
5	Correct	2 ms	5076 KB	Output is correct
6	Correct	2 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	5 ms	5076 KB	Output is correct
10	Correct	2 ms	5076 KB	Output is correct
11	Correct	3 ms	5076 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	1081 ms	38672 KB	Output is correct
14	Correct	1545 ms	50420 KB	Output is correct
15	Correct	1085 ms	38648 KB	Output is correct
16	Correct	343 ms	38596 KB	Output is correct
17	Correct	1452 ms	40436 KB	Output is correct
18	Correct	315 ms	38796 KB	Output is correct
19	Correct	1815 ms	50852 KB	Output is correct
20	Correct	267 ms	39264 KB	Output is correct
21	Correct	2 ms	5036 KB	Output is correct
22	Correct	1172 ms	38668 KB	Output is correct
23	Correct	1514 ms	52636 KB	Output is correct
24	Correct	1132 ms	38732 KB	Output is correct
25	Correct	340 ms	38596 KB	Output is correct
26	Correct	1568 ms	40668 KB	Output is correct
27	Correct	260 ms	39044 KB	Output is correct
28	Correct	1615 ms	46472 KB	Output is correct
29	Correct	241 ms	39228 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	5460 KB	Output is correct
33	Correct	6 ms	5460 KB	Output is correct
34	Correct	7 ms	5332 KB	Output is correct
35	Correct	6 ms	5332 KB	Output is correct
36	Correct	6 ms	5332 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	5508 KB	Output is correct
40	Correct	6 ms	5448 KB	Output is correct
41	Correct	6 ms	5508 KB	Output is correct
42	Correct	4 ms	5508 KB	Output is correct
43	Correct	7 ms	5588 KB	Output is correct
44	Correct	4 ms	5460 KB	Output is correct
45	Correct	2 ms	5076 KB	Output is correct
46	Correct	1202 ms	38816 KB	Output is correct
47	Correct	1495 ms	52600 KB	Output is correct
48	Correct	1096 ms	38740 KB	Output is correct
49	Correct	1153 ms	38740 KB	Output is correct
50	Correct	1183 ms	38680 KB	Output is correct
51	Correct	1127 ms	45172 KB	Output is correct
52	Correct	1159 ms	43984 KB	Output is correct
53	Correct	367 ms	45128 KB	Output is correct
54	Correct	1425 ms	46768 KB	Output is correct
55	Correct	1160 ms	45152 KB	Output is correct
56	Correct	1035 ms	44172 KB	Output is correct
57	Correct	299 ms	45340 KB	Output is correct
58	Correct	1736 ms	53444 KB	Output is correct
59	Correct	253 ms	45772 KB	Output is correct
60	Correct	2 ms	5076 KB	Output is correct
61	Correct	1130 ms	47700 KB	Output is correct
62	Correct	1571 ms	58464 KB	Output is correct
63	Correct	1139 ms	46412 KB	Output is correct
64	Correct	1147 ms	47744 KB	Output is correct
65	Correct	1111 ms	46508 KB	Output is correct
66	Correct	1142 ms	47820 KB	Output is correct
67	Correct	1232 ms	46476 KB	Output is correct
68	Correct	390 ms	47780 KB	Output is correct
69	Correct	1472 ms	49200 KB	Output is correct
70	Correct	1205 ms	47660 KB	Output is correct
71	Correct	982 ms	47044 KB	Output is correct
72	Correct	329 ms	48572 KB	Output is correct
73	Correct	1671 ms	54568 KB	Output is correct
74	Correct	277 ms	49880 KB	Output is correct