oj.uz

Submission #298525

# Submission time Handle Problem Language Result Execution time Memory
298525 2020-09-13T04:26:04 Z LifeHappen__ Džumbus (COCI19_dzumbus) C++14
110 / 110
 63 ms 19064 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}

#define forinc(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define fordec(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)

#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

const int N=1005;
const int inf=1e18;
int n,m,a[N];
vector<int> ad[N];
int f[N][N][2],dd[N],sz[N],ans[N];

void Min(int &x,int y){
   x=min(x,y);
}

void dfs(int u){
   dd[u]=1;
   sz[u]=1;
   forinc(i,1,n) f[u][i][0]=f[u][i][1]=inf;
   f[u][0][1]=inf;
   forv(v,ad[u]) if(!dd[v]){
      dfs(v);
      fordec(i,sz[u],0){
         for(int j=0; j<=sz[v] && i+j<=n; ++j){
            Min(f[u][i+j][0], f[u][i][0]+min(f[v][j][1],f[v][j][0]));
            Min(f[u][i+j][1], f[u][i][1]+min(f[v][j][1],f[v][j][0]));
            Min(f[u][i+j+1][1], f[u][i][0]+f[v][j][1]+a[u]);
            Min(f[u][i+j+1][1], f[u][i][1]+f[v][j][0]+a[v]);
            Min(f[u][i+j+2][1], f[u][i][0]+f[v][j][0]+a[v]+a[u]);
         }
      }
      sz[u]+=sz[v];
   }
}

int32_t main(){
   fasty;

   cin>>n>>m;
   forinc(i,1,n) cin>>a[i];
   forinc(i,1,m){
      int u,v; cin>>u>>v;
      ad[u].pb(v); ad[v].pb(u);
   }
   forinc(i,1,n) ans[i]=inf;
   forinc(i,1,n) if(!dd[i]){
      dfs(i);
      fordec(j,n,0){
         for(int u=0; u+j<=n && u<=sz[i]; ++u){
            Min(ans[j+u], ans[j]+min(f[i][u][0], f[i][u][1]));
         }
      }
   }
   fordec(i,n-1,0) ans[i]=min(ans[i],ans[i+1]);
   int ri=n;
   //forinc(i,1,n) cerr<<ans[i]<<' ';
   forinc(i,0,n) if(ans[i]>1e9){
      ri=i-1;
      break;
   }
   int que; cin>>que; forinc(_,1,que){
      int x; cin>>x;
      int l=0, r=ri, ret=0;
      while(l<=r){
         int mid=l+(r-l)/2;
         if(ans[mid]<=x) ret=mid, l=mid+1;
         else r=mid-1;
      }
      cout<<ret<<'\n';
   }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16256 KB Output is correct
2 Correct 19 ms 16256 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16256 KB Output is correct
2 Correct 19 ms 16256 KB Output is correct
3 Correct 58 ms 18424 KB Output is correct
4 Correct 63 ms 19064 KB Output is correct
5 Correct 62 ms 18680 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1784 KB Output is correct
2 Correct 39 ms 1528 KB Output is correct
3 Correct 41 ms 1400 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16256 KB Output is correct
2 Correct 19 ms 16256 KB Output is correct
3 Correct 58 ms 18424 KB Output is correct
4 Correct 63 ms 19064 KB Output is correct
5 Correct 62 ms 18680 KB Output is correct
6 Correct 39 ms 1784 KB Output is correct
7 Correct 39 ms 1528 KB Output is correct
8 Correct 41 ms 1400 KB Output is correct
9 Correct 51 ms 18296 KB Output is correct
10 Correct 58 ms 18936 KB Output is correct
11 Correct 53 ms 18680 KB Output is correct