Submission #3729589


Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef pair<int, P> Pi;
ll a[100002], b[100002];
int par[100002];
int rk[100002];
ll size[100002];
ll mx[100002];
int num[100002];
int c;
P pab[200002];
vector<int> v[200002];
void add(int x, int y){
  //v[x].push_back(y);
  v[y].push_back(x);
}
void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
		rk[i]=0;
      size[i]=b[i];
      mx[i]=a[i];
      num[i]=i;
	}
}
 
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
 
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
      add(num[x], c);
      add(num[y], c);
      num[y]=c;
      size[y]+=size[x];
      mx[y]=max(mx[y], mx[x]);
      pab[c]=P(mx[y], size[y]);
	}else{
		par[y]=x;
      add(num[x], c);
      add(num[y], c);
      num[x]=c;
      size[x]+=size[y];
      mx[x]=max(mx[y], mx[x]);
      pab[c]=P(mx[x], size[x]);
		if(rk[x]==rk[y]) rk[x]++;
	}
  c++;
}
 
bool same(int x, int y){
	return find(x)==find(y);
}
ll x0;
//bool used0[200002];
bool dfs(int x){
  //used0[x]=1;
  if(v[x].empty()) return true;
  bool ok=0;
  for(auto y:v[x]){
    //if(used0[y]) continue;
    if(!dfs(y)) continue;
    if(x0+pab[y].second>=pab[x].first){
      ok=1;
    }
  }
  return ok;
}
int main()
{
	int n, m;
  cin>>n>>m;
  c=n;
  P pa[100000];
  ll s=0;
  for(int i=0; i<n; i++){
    cin>>a[i]>>b[i];
    a[i]-=b[i];
    s+=b[i];
    pa[i]=P(a[i], i);
    pab[i]=P(a[i], b[i]);
  }
  if(n==1){
    if(a[0]>=0) cout<<a[0]+b[0]<<endl;
    else cout<<b[0]<<endl;
    return 0;
  }
  sort(pa, pa+n);
  vector<int> g[100000];
  for(int i=0; i<m; i++){
    int u, v;
    cin>>u>>v;
    u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  bool used[100000]={};
  init(n);
  for(int i=0; i<n; i++){
    int x=pa[i].second;
    used[x]=1;
    for(auto y:g[x]){
      if(used[y]){
        if(!same(x, y)) unite(x, y);
      }
    }
  }
  /*for(int i=0; i<c; i++){
    cout<<i<<" ";
    for(auto y:v[i]) cout<<y<<" ";
    cout<<endl;
  }*/
  ll x1=0, x2=1e9;
  while(x1!=x2){
    x0=(x1+x2)/2;
    if(dfs(c-1)) x2=x0;
    else x1=x0+1;
  }
  cout<<x1+s<<endl;
	return 0;
}

Submission Info

Submission Time
Task F - Donation
User chocorusk
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 2569 Byte
Status AC
Exec Time 457 ms
Memory 28412 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 54
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt
Case Name Status Exec Time Memory
sample_01.txt AC 6 ms 14464 KB
sample_02.txt AC 7 ms 14464 KB
sample_03.txt AC 7 ms 14464 KB
subtask_1_01.txt AC 5 ms 9984 KB
subtask_1_02.txt AC 12 ms 14720 KB
subtask_1_03.txt AC 49 ms 15616 KB
subtask_1_04.txt AC 7 ms 14464 KB
subtask_1_05.txt AC 7 ms 14464 KB
subtask_1_06.txt AC 7 ms 14464 KB
subtask_1_07.txt AC 7 ms 14464 KB
subtask_1_08.txt AC 7 ms 14464 KB
subtask_1_09.txt AC 7 ms 14464 KB
subtask_1_10.txt AC 8 ms 14464 KB
subtask_1_11.txt AC 7 ms 14464 KB
subtask_1_12.txt AC 7 ms 14464 KB
subtask_1_13.txt AC 42 ms 15360 KB
subtask_1_14.txt AC 15 ms 14720 KB
subtask_1_15.txt AC 51 ms 16256 KB
subtask_1_16.txt AC 276 ms 22400 KB
subtask_1_17.txt AC 63 ms 16640 KB
subtask_1_18.txt AC 279 ms 23168 KB
subtask_1_19.txt AC 79 ms 17408 KB
subtask_1_20.txt AC 272 ms 23680 KB
subtask_1_21.txt AC 251 ms 26876 KB
subtask_1_22.txt AC 98 ms 20224 KB
subtask_1_23.txt AC 94 ms 19968 KB
subtask_1_24.txt AC 71 ms 18176 KB
subtask_1_25.txt AC 60 ms 15872 KB
subtask_1_26.txt AC 281 ms 20992 KB
subtask_1_27.txt AC 228 ms 19968 KB
subtask_1_28.txt AC 16 ms 14848 KB
subtask_1_29.txt AC 190 ms 20864 KB
subtask_1_30.txt AC 275 ms 22656 KB
subtask_1_31.txt AC 31 ms 15488 KB
subtask_1_32.txt AC 355 ms 22784 KB
subtask_1_33.txt AC 345 ms 22784 KB
subtask_1_34.txt AC 327 ms 22784 KB
subtask_1_35.txt AC 348 ms 22784 KB
subtask_1_36.txt AC 348 ms 22656 KB
subtask_1_37.txt AC 330 ms 22656 KB
subtask_1_38.txt AC 305 ms 28412 KB
subtask_1_39.txt AC 261 ms 28156 KB
subtask_1_40.txt AC 262 ms 28412 KB
subtask_1_41.txt AC 253 ms 27516 KB
subtask_1_42.txt AC 372 ms 22656 KB
subtask_1_43.txt AC 317 ms 22656 KB
subtask_1_44.txt AC 335 ms 22656 KB
subtask_1_45.txt AC 346 ms 22656 KB
subtask_1_46.txt AC 348 ms 22784 KB
subtask_1_47.txt AC 377 ms 22784 KB
subtask_1_48.txt AC 457 ms 22784 KB