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 |
|
|
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 |