# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
579760 |
2022-06-19T19:10:27 Z |
AGE |
Džumbus (COCI19_dzumbus) |
C++14 |
|
370 ms |
86856 KB |
#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pb push_back
using namespace std;
const int N=1e6,M=2e3+1,mod=1e9+7;
int dp[M][M][2],a[N],parr[N],son[N];
vector<int>adj[N];
int node2;
bool ok(int mid,int val){
for(int j=0;j<2;j++){
if(dp[node2][mid][j]<=val)
return 1;
}
return 0;
}
void dfs2(int node,int par){
for(auto x:adj[node]){
if(x==par){
parr[node]=par;
continue;
}
son[node]=x;
dfs2(x,node);
}
}
void dfs(int node,int par){
//cout<<"#%&$%@^@#^$%^"<<endl;
if(son[node]==node)
return ;
for(int j=0;j<1000;j++){
dp[son[node]][j+1][1]=min(dp[son[node]][j+1][1],dp[node][j][1]+a[son[node]]);
dp[son[node]][j][0]=min(dp[son[node]][j][0],dp[node][j][1]);
if(j+2<=1000)
dp[son[son[node]]][j+2][1]=min(dp[son[son[node]]][j+2][1],dp[node][j][0]+a[son[node]]+a[son[son[node]]]);
dp[son[node]][j][0]=min(dp[son[node]][j][0],dp[node][j][0]);
}
dfs(son[node],node);
}
main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
int node=1,par=0;
for(int i=0;i<=2000;i++)
for(int j=0;j<=2000;j++)
for(int k=0;k<2;k++)
dp[i][j][k]=1e18;
for(int i=1;i<=n;i++)
if(adj[i].size()==1)
node=i;
for(int i=1;i<=n;i++)
if(adj[i].size()==1&&node!=i)
node2=i;
dfs2(node,0);
son[node2]=node2;
dp[node][0][0]=0;
dp[son[node]][2][1]=a[node]+a[son[node]];
dfs(node,0);
int q;
cin>>q;
for(int i=999;i>=0;i--)
for(int j=0;j<2;j++)
dp[node2][i][j]=min(dp[node2][i][j],dp[node2][i+1][j]);
while(q--){
int val;
cin>>val;
int ans=-1e18;
int l=0,r=1000;
while(l<r){
int okk=0;
int mid=(l+r+1)/2;
if(ok(mid,val))
l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
return 0;
}
Compilation message
dzumbus.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
61 | main(){
| ^~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:120:17: warning: unused variable 'okk' [-Wunused-variable]
120 | int okk=0;
| ^~~
dzumbus.cpp:116:13: warning: unused variable 'ans' [-Wunused-variable]
116 | int ans=-1e18;
| ^~~
dzumbus.cpp:80:16: warning: unused variable 'par' [-Wunused-variable]
80 | int node=1,par=0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
86496 KB |
Output is correct |
2 |
Incorrect |
45 ms |
86536 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
86496 KB |
Output is correct |
2 |
Incorrect |
45 ms |
86536 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
370 ms |
86856 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
86496 KB |
Output is correct |
2 |
Incorrect |
45 ms |
86536 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |