| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 868536 | huynhyen1609 | Džumbus (COCI19_dzumbus) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
..
.:^!7?JJJYJJJJ?77!!~^.
.:~7JYYJYYJJ?77?J??JY?JYY5YY?7~:.
:!J5YJ??777J?J?????7J?J?7J?J?JYYYYY?~.
:?5JJ???77!?77?J??J7?7???JJJJ?J777??JYJY?!.
^J5YYJJJ77?!7!7!77JJJJ?J77??Y???77!!777!7?JY5?^
~JYY??J7??7J?7?!7!7???J?77!777J?JY?J7777?7?????5PY^
^Y5J??J??!!???J??77777????J?J77?YY?!~^::::::^!77??YPG7.
!PY?777?77!7!7J?7!7?????JJ??7J??J^:. .:!7?75GY:
.JPJ!7!7?7?7!7!????????J?7??7J?YJ~. .:!7?JGP^
.JP?!7!!??7J7!!!?7J????7J7!!?!?7?7. . ^??YG5:
!P??7777?77??777?7?!7!777!?7J??J?^ :~~: . ^?7YGY.
:PY7??77!7~~:::.....:^^~!7??????J?^ . .7PGGPY: . !?JPB~
.Y5!!Y77!~:.. .:~7JJJ??J!. . . .5GGGGP^ ..:J?JBJ
~G?!!?7!^. .^7JJYYJ7:. . ..:~???~^^:..77?G5.
!G!7?77: ..?J7~^~!77: . .. ..^~~~~~~~:.!75B!
!P77J7^ ..~?:::^~!7?^ ........^~^^^^^:.^JYG?.
!G???!: .~77!:. ..7?7?77~:....................^JPJ~
:P5??7: .JGGGGP! ...... ..................:^!JP?^
7BJ7J~ .JGGGGG~ . .....................::::^!7?JJ?!^.
.YG?Y7^ .~7??~:::. .. .... ... ....::::::::::::^?~^!?J7:
:PPJ??: ..:^^^^^^: . .... ....::::^::::::::.:::^JP~..:75~
:YGYJ?^. .^^^^^^^:. .....:::::::::::...:::..:.::JP!~~7Y~
~PP5J?^...::::.... ......::::::::.:.::.:::::.:::::::::^JP?7~.
:75P5YJ!~^^^^!:...::^:::::::...:......::.....::::::::^^5?
?G?Y55PP5YJ!^:::::::::..:..:.:....:...:....::..::::^^7G^
~P!^:::::.::::::::::::::...:.::::.:.:::::.:.......:::^PY
:!JJ7~^::::::::::::::::..:.:.::.:::::...::.........:.JP.
:5P?^:^:::::^::::::::::::.::::::.:.::.::........::7P:
.P7::::::::::^::^^::::::::::::::::.:.........:::::J5.
. ^G~:^^:::::::^:^^^^^:::::::::^:::::::::::::::^^::75^
:P!^^^^^^^^:^^^^^^:^:::::^:::^:::::::::::::::^^7JY^
.!5~^~^^^^^^^^^:^^^^^^^^:^^^^:^^^^^^^^^^^^^^~?55G?
~J?~~~^^~~^~~~^^^^^^^:^^^~^^^^^^^^~~!!!?Y55GP?J!.
.~PYJ?77?7777!!!!!!!!!!!!7777??JJJJJ5PP5??J^ ..
.777?5J??YYYYY5?7777!!!!~!~~^^::. .::
:!!~:.:^^:
PENGUIN SO CUTE, I LOVE PENGUIN
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define NAME "coctail"
#define int long long
#define ii pair<int,int>
#define i(x) array<int,x>
const int oo=1e9;
const int mod=1e9+7;
const int N=1e3;
const int LG=18;
const int Sqrt=350;
//int hx[]={0,0,1,-1,1,1,-1,-1},hy[]={1,-1,0,0,1,-1,1,-1};
int getbit(int x,int i)
{
return (x>>i)&1;
}
int add(int x,int y)
{
x+=y;
if(x>=mod)x-=mod;
return x;
}
int del(int x,int y)
{
x-=y;
if(x<0)x+=mod;
return x;
}
int mul(int x,int y)
{
return x*y%mod;
}
int n,m,q,d[N+5],dp[2][N+5][N+5],sz[N+5];
vector<int>graph[N+5];
void dfs(int u,int pre)
{
sz[u]=1;
dp[0][u][0]=0;
for(int v:graph[u])
if(v!=pre)
{
if(dp[0][v][0]==oo)dfs(v,u);
for(int i=sz[u];i>=0;--i)
{
for(int j=0;j<=sz[v];++j)
{
dp[0][u][i+j]=min(dp[0][u][i+j],dp[0][u][i]+min(dp[0][v][j],dp[1][v][j]));
dp[1][u][i+j]=min(dp[1][u][i+j],dp[1][u][i]+min(dp[0][v][j],dp[1][v][j]));
dp[1][u][i+j+1]=min({dp[1][u][i+j+2],dp[0][u][i]+d[u]+dp[1][v][j],dp[1][u][i]+dp[0][v][j]+d[v]});
dp[1][u][i+j+2]=min(dp[1][u][i+j+2],dp[0][u][i]+d[u]+dp[0][v][j]+d[v]});
}
}
sz[u]+=sz[v];
}
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
//freopen(""NAME".inp","r",stdin);
//freopen(""NAME".out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;++i)cin>>d[i];
for(int i=1;i<=m;++i)
{
int u,v;cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
}
for(int i=0;i<=n;++i)
for(int j=0;j<=n;++j)dp[0][i][j]=dp[1][i][j]=oo;
for(int i=1;i<=n;++i)
if(dp[0][i][0]==oo)
{
dfs(i,0);
graph[0].push_back(i);
}
d[0]=oo;
dfs(0,0);
cin>>q;
vector<int>vec;
int res=oo;
for(int i=n;i>=2;--i)
{
res=min(res,dp[0][0][i]);
vec.push_back(res);
}
sort(vec.begin(),vec.end());
while(q--)
{
int s;cin>>s;
int tmp=upper_bound(v.begin(),v.end(),s)-v.begin()-1;
if(tmp==1)tmp=0;
cout<<tmp<<'\n';
}
}
/*
ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3
*/