fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5.  
  6. const ll maxA=2e14;
  7. const int maxN=2e5;
  8. vector<int> v[maxN+1]; // adjacency list
  9. ll cst[maxN+1]; // each node -> cost
  10. ll cnt[maxN+1]={0}; // the cost to remove node ( original )
  11. ll tmp[maxN+1]; // the cost to remove node
  12. deque<int> dq; // the node to remove
  13. int N, M, a, b;
  14.  
  15. bool check(ll num){
  16. 	ll count=0;
  17.  
  18. 	for(int i=1;i<=N;i++){
  19. 		tmp[i]=cnt[i];
  20. 		if( tmp[i]<=num ){
  21. 			dq.push_back(i);
  22. 			tmp[i]=-1;
  23. 			count++;
  24. 		}	
  25. 	}
  26. 	while( !dq.empty() ){
  27. 		int n=dq.front();
  28. 		dq.pop_front();
  29.  
  30. 		for(int i=0;i<v[n].size();i++){
  31. 			int now=v[n][i];
  32. 			if( tmp[ now ]<0 ) continue;
  33. 			tmp[ now ]-=cst[n];
  34. 			if( tmp[now]<=num ){
  35. 				dq.push_back(now);
  36. 				tmp[now]=-1;
  37. 				count++;
  38. 			}
  39. 		}
  40. 	}
  41. 	if( count==N ) return true;
  42. 	return false;
  43. }
  44.  
  45. int main() {
  46. 	cin>>N>>M;
  47. 	for(int i=1;i<=N;i++)
  48. 		cin>>cst[i];
  49. 	for(int i=0;i<M;i++){
  50. 		cin>>a>>b;
  51. 		v[a].push_back(b);
  52. 		v[b].push_back(a);
  53. 	}
  54. 	ll L=maxA;
  55. 	ll R=0;
  56. 	for(int i=1;i<=N;i++){
  57. 		for(int j=0;j<v[i].size();j++){
  58. 			cnt[i]+=cst[ v[i][j] ];
  59. 		}
  60. 		L=min(L,cnt[i]);
  61. 		R=max(R,cnt[i]);
  62. 	}
  63.  
  64. 	ll ans;
  65. 	while( L<=R ){
  66. 		ll M=(L+R)/2;
  67. 		if( check(M) ){
  68. 			R=M-1;
  69. 			ans=M;
  70. 		}
  71. 		else L=M+1;
  72. 	}
  73. 	cout<<ans;
  74.  
  75. 	//for(int i=1;i<=N;i++)
  76. 	//	cout<<cnt[i]<<' ';
  77.  
  78.  
  79. }
Success #stdin #stdout 0.01s 11600KB
comments (?)
stdin
copy 
7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7
stdout
copy 
1199
https://ideone.com/pDjbQL
Erasing Vertices 2 AtCoder - abc267_e
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!