oj.uz

Submission #830133

# Submission time Handle Problem Language Result Execution time Memory
830133 2023-08-18T19:48:48 Z MohamedAhmed04 Designated Cities (JOI19_designated_cities) C++14
22 / 100
 1711 ms 52716 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)
{
	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:159:30: warning: unused variable 'w' [-Wunused-variable]
  159 |   int child = childd.first , w = childd.second ;
      |                              ^
designated_cities.cpp:190:30: warning: unused variable 'w' [-Wunused-variable]
  190 |   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 2 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 2 ms 5076 KB Output is correct
10 Correct 3 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 854 ms 38744 KB Output is correct
3 Correct 1438 ms 50420 KB Output is correct
4 Correct 1122 ms 38736 KB Output is correct
5 Correct 339 ms 38616 KB Output is correct
6 Correct 1142 ms 40340 KB Output is correct
7 Correct 282 ms 38720 KB Output is correct
8 Correct 1711 ms 50852 KB Output is correct
9 Correct 291 ms 39260 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 912 ms 38740 KB Output is correct
3 Correct 1489 ms 52544 KB Output is correct
4 Correct 1176 ms 38640 KB Output is correct
5 Correct 336 ms 38700 KB Output is correct
6 Correct 1193 ms 40760 KB Output is correct
7 Correct 274 ms 39120 KB Output is correct
8 Correct 1440 ms 46428 KB Output is correct
9 Correct 252 ms 39228 KB Output is correct

Subtask #4
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 2 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 2 ms 5076 KB Output is correct
10 Correct 3 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 6 ms 5460 KB Output is correct
16 Correct 6 ms 5432 KB Output is correct
17 Correct 6 ms 5340 KB Output is correct
18 Correct 6 ms 5332 KB Output is correct
19 Incorrect 6 ms 5332 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 854 ms 38744 KB Output is correct
3 Correct 1438 ms 50420 KB Output is correct
4 Correct 1122 ms 38736 KB Output is correct
5 Correct 339 ms 38616 KB Output is correct
6 Correct 1142 ms 40340 KB Output is correct
7 Correct 282 ms 38720 KB Output is correct
8 Correct 1711 ms 50852 KB Output is correct
9 Correct 291 ms 39260 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 912 ms 38740 KB Output is correct
12 Correct 1489 ms 52544 KB Output is correct
13 Correct 1176 ms 38640 KB Output is correct
14 Correct 336 ms 38700 KB Output is correct
15 Correct 1193 ms 40760 KB Output is correct
16 Correct 274 ms 39120 KB Output is correct
17 Correct 1440 ms 46428 KB Output is correct
18 Correct 252 ms 39228 KB Output is correct
19 Correct 2 ms 5076 KB Output is correct
20 Correct 881 ms 38744 KB Output is correct
21 Correct 1601 ms 52716 KB Output is correct
22 Correct 1136 ms 38740 KB Output is correct
23 Correct 878 ms 38796 KB Output is correct
24 Incorrect 953 ms 38676 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
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 2 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 2 ms 5076 KB Output is correct
10 Correct 3 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 854 ms 38744 KB Output is correct
14 Correct 1438 ms 50420 KB Output is correct
15 Correct 1122 ms 38736 KB Output is correct
16 Correct 339 ms 38616 KB Output is correct
17 Correct 1142 ms 40340 KB Output is correct
18 Correct 282 ms 38720 KB Output is correct
19 Correct 1711 ms 50852 KB Output is correct
20 Correct 291 ms 39260 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 912 ms 38740 KB Output is correct
23 Correct 1489 ms 52544 KB Output is correct
24 Correct 1176 ms 38640 KB Output is correct
25 Correct 336 ms 38700 KB Output is correct
26 Correct 1193 ms 40760 KB Output is correct
27 Correct 274 ms 39120 KB Output is correct
28 Correct 1440 ms 46428 KB Output is correct
29 Correct 252 ms 39228 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 6 ms 5460 KB Output is correct
34 Correct 6 ms 5432 KB Output is correct
35 Correct 6 ms 5340 KB Output is correct
36 Correct 6 ms 5332 KB Output is correct
37 Incorrect 6 ms 5332 KB Output isn't correct
38 Halted 0 ms 0 KB -