Submission #399802

#TimeUsernameProblemLanguageResultExecution timeMemory
399802nguotDžumbus (COCI19_dzumbus)C++14
110 / 110
59 ms19088 KiB
//Vong 2 doi tuyen QG #include <bits/stdc++.h> using namespace std; #define int long long #define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;}) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){return l+rng()%(r-l+1);} #define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define fori(x,a,b) for(int x=a;x<=b;x++) #define ford(x,a,b) for(int x=a;x>=b;x--) #define forv(a,b) for(auto&a:b) #define fi first #define se second #define pb push_back #define ii pair<int,int> #define mt make_tuple #define all(a) a.begin(),a.end() #define reset(f,x) memset(f,x,sizeof(f)) #define getbit(x,i) ((x>>i)&1) #define batbit(x,i) (x|(1ll<<i)) #define tatbit(x,i) (x&~(1<<i)) #define gg exit(0); const int maxn = 1e3 + 10; int n,m,q,dd[maxn],a[maxn],tg[maxn][2],f[maxn][maxn][2],ans[maxn]; vector<int> ke[maxn]; int dfs(int u,int pr) { dd[u] = 1; int szu = 1; fori(i,1,n) f[u][i][0] = f[u][i][1] = 1e15; f[u][0][0] = 0; f[u][0][1] = 1e15; forv(v,ke[u]) if(v!=pr) { int szv = dfs(v,u); ford(i,szu,0) for(int j=0;i+j<=n&&j<=szv;j++) { f[u][i+j][0] = min(f[u][i+j][0],f[u][i][0] + min(f[v][j][0],f[v][j][1])); f[u][i+j][1] = min(f[u][i+j][1],f[u][i][1] + min(f[v][j][0],f[v][j][1])); f[u][i+j+1][1] = min(f[u][i+j+1][1],f[u][i][0] + a[u] + f[v][j][1]); f[u][i+j+1][1] = min(f[u][i+j+1][1],f[u][i][1] + f[v][j][0] + a[v]); f[u][i+j+2][1] = min(f[u][i+j+2][1],f[u][i][0] + f[v][j][0] + a[u] + a[v]); } szu+=szv; } return szu; } main() { //freopen("task.inp","r",stdin); fasty; cin>>n>>m; fori(i,1,n) cin>>a[i]; fori(i,1,m) { int x,y;cin>>x>>y; ke[x].pb(y),ke[y].pb(x); } fori(i,1,n) ans[i] = 1e15; fori(v,1,n) if(!dd[v]) { int szv = dfs(v,0); ford(j,n,0) for(int i=0;i+j<=n && i<=szv;i++) ans[i+j] = min(ans[i+j],ans[j] + min(f[v][i][0],f[v][i][1])); } ford(i,n-1,0) ans[i] = min(ans[i+1],ans[i]); int maxval = n; fori(i,0,n) if(ans[i]>1e9) { maxval = i-1; break; } int t;cin>>t; while(t--) { int x;cin>>x; int l=0,r=maxval,res=0; while(l<=r) { int mid = (l+r)/2; if(ans[mid] > x) r=mid-1; else res=mid,l=mid+1; } cout<<res<<"\n"; } }

Compilation message (stderr)

dzumbus.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main()
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...