oj.uz

Submission #830131

# Submission time Handle Problem Language Result Execution time Memory
830131 2023-08-18T19:47:14 Z MohamedAhmed04 Designated Cities (JOI19_designated_cities) C++14
22 / 100
 1523 ms 59084 KB 
#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)
{
	if(l == r)
	{
		tree[node] = {val3[id[l]] , id[l]} , lazy[node] = 0 ;
		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:162:30: warning: unused variable 'w' [-Wunused-variable]
  162 |   int child = childd.first , w = childd.second ;
      |                              ^
designated_cities.cpp:193:30: warning: unused variable 'w' [-Wunused-variable]
  193 |   int child = childd.first , w = childd.second ;
      |                              ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5064 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 2 ms 5024 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 846 ms 38732 KB Output is correct
3 Correct 1363 ms 50316 KB Output is correct
4 Correct 1091 ms 38688 KB Output is correct
5 Correct 371 ms 38636 KB Output is correct
6 Correct 1069 ms 40380 KB Output is correct
7 Correct 349 ms 38408 KB Output is correct
8 Correct 1523 ms 50760 KB Output is correct
9 Correct 229 ms 38204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 901 ms 38744 KB Output is correct
3 Correct 1380 ms 58844 KB Output is correct
4 Correct 1137 ms 43724 KB Output is correct
5 Correct 319 ms 45068 KB Output is correct
6 Correct 1120 ms 47044 KB Output is correct
7 Correct 241 ms 44304 KB Output is correct
8 Correct 1381 ms 53008 KB Output is correct
9 Correct 243 ms 44280 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5064 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 2 ms 5024 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 5332 KB Output is correct
14 Correct 6 ms 5460 KB Output is correct
15 Correct 7 ms 5460 KB Output is correct
16 Correct 6 ms 5460 KB Output is correct
17 Correct 8 ms 5460 KB Output is correct
18 Correct 6 ms 5508 KB Output is correct
19 Incorrect 8 ms 5460 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 846 ms 38732 KB Output is correct
3 Correct 1363 ms 50316 KB Output is correct
4 Correct 1091 ms 38688 KB Output is correct
5 Correct 371 ms 38636 KB Output is correct
6 Correct 1069 ms 40380 KB Output is correct
7 Correct 349 ms 38408 KB Output is correct
8 Correct 1523 ms 50760 KB Output is correct
9 Correct 229 ms 38204 KB Output is correct
10 Correct 2 ms 5076 KB Output is correct
11 Correct 901 ms 38744 KB Output is correct
12 Correct 1380 ms 58844 KB Output is correct
13 Correct 1137 ms 43724 KB Output is correct
14 Correct 319 ms 45068 KB Output is correct
15 Correct 1120 ms 47044 KB Output is correct
16 Correct 241 ms 44304 KB Output is correct
17 Correct 1381 ms 53008 KB Output is correct
18 Correct 243 ms 44280 KB Output is correct
19 Correct 3 ms 5096 KB Output is correct
20 Correct 851 ms 45140 KB Output is correct
21 Correct 1402 ms 59084 KB Output is correct
22 Correct 1067 ms 43760 KB Output is correct
23 Correct 898 ms 45200 KB Output is correct
24 Incorrect 867 ms 43980 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5064 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 2 ms 5024 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 846 ms 38732 KB Output is correct
14 Correct 1363 ms 50316 KB Output is correct
15 Correct 1091 ms 38688 KB Output is correct
16 Correct 371 ms 38636 KB Output is correct
17 Correct 1069 ms 40380 KB Output is correct
18 Correct 349 ms 38408 KB Output is correct
19 Correct 1523 ms 50760 KB Output is correct
20 Correct 229 ms 38204 KB Output is correct
21 Correct 2 ms 5076 KB Output is correct
22 Correct 901 ms 38744 KB Output is correct
23 Correct 1380 ms 58844 KB Output is correct
24 Correct 1137 ms 43724 KB Output is correct
25 Correct 319 ms 45068 KB Output is correct
26 Correct 1120 ms 47044 KB Output is correct
27 Correct 241 ms 44304 KB Output is correct
28 Correct 1381 ms 53008 KB Output is correct
29 Correct 243 ms 44280 KB Output is correct
30 Correct 2 ms 5076 KB Output is correct
31 Correct 6 ms 5332 KB Output is correct
32 Correct 6 ms 5460 KB Output is correct
33 Correct 7 ms 5460 KB Output is correct
34 Correct 6 ms 5460 KB Output is correct
35 Correct 8 ms 5460 KB Output is correct
36 Correct 6 ms 5508 KB Output is correct
37 Incorrect 8 ms 5460 KB Output isn't correct
38 Halted 0 ms 0 KB -