oj.uz

Submission #830117

# Submission time Handle Problem Language Result Execution time Memory
830117 2023-08-18T19:03:56 Z MohamedAhmed04 Designated Cities (JOI19_designated_cities) C++14
6 / 100
 2000 ms 45520 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
 
#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] ;
 
void build(int node , int l , int r)
{
	if(l == r)
	{
		tree[node] = {0 , 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 || from > to)
		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] , id[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 ;
		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 ;
	update(1 , 1 , cursz , in[node] , out[node] , val[node]) ;
}
 
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] = 0 ;
	build(1 , 1 , cursz) ;
	dfs(centroid , 0) ;
	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 = id[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:164:30: warning: unused variable 'w' [-Wunused-variable]
  164 |   int child = childd.first , w = childd.second ;
      |                              ^
designated_cities.cpp:195:30: warning: unused variable 'w' [-Wunused-variable]
  195 |   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 2 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5056 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5096 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5116 KB Output is correct
9 Correct 2 ms 5036 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 1191 ms 37076 KB Output is correct
3 Correct 1757 ms 45520 KB Output is correct
4 Correct 1553 ms 37176 KB Output is correct
5 Correct 448 ms 37088 KB Output is correct
6 Correct 1521 ms 38220 KB Output is correct
7 Correct 374 ms 36812 KB Output is correct
8 Execution timed out 2089 ms 45056 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Incorrect 1237 ms 37172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory 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 5056 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5096 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5116 KB Output is correct
9 Correct 2 ms 5036 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 Incorrect 8 ms 5332 KB Output isn't correct
14 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 1191 ms 37076 KB Output is correct
3 Correct 1757 ms 45520 KB Output is correct
4 Correct 1553 ms 37176 KB Output is correct
5 Correct 448 ms 37088 KB Output is correct
6 Correct 1521 ms 38220 KB Output is correct
7 Correct 374 ms 36812 KB Output is correct
8 Execution timed out 2089 ms 45056 KB Time limit exceeded
9 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 2 ms 5076 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5056 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5096 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 3 ms 5116 KB Output is correct
9 Correct 2 ms 5036 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 1191 ms 37076 KB Output is correct
14 Correct 1757 ms 45520 KB Output is correct
15 Correct 1553 ms 37176 KB Output is correct
16 Correct 448 ms 37088 KB Output is correct
17 Correct 1521 ms 38220 KB Output is correct
18 Correct 374 ms 36812 KB Output is correct
19 Execution timed out 2089 ms 45056 KB Time limit exceeded
20 Halted 0 ms 0 KB -