# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
89970 |
2018-12-19T11:33:36 Z |
vex |
Paprike (COI18_paprike) |
C++14 |
|
94 ms |
63464 KB |
#include <bits/stdc++.h>
#define maxn 1000005
#define pii pair<int,int>
#define ljutina first
#define brojSecenja second
#define par second.second
#define node second.first
using namespace std;
int n,k;
int h[maxn];
vector<pair<pii,pii>>adj[maxn];
pii dp[maxn];
bool cmp(pair<pii,pii> ff,pair<pii,pii> ss)
{
if(ff.par==1)return true;
if(ss.par==1)return false;
return ff.first.ljutina<=ss.first.ljutina;
}
void dfs(int v,int p)
{
dp[v].ljutina=0;
dp[v].brojSecenja=0;
bool leaf=true;
for(auto x:adj[v])
{
int u=x.node;
if(u==p)
{
x.par=1;
continue;
}
dfs(u,v);
leaf=false;
}
dp[v].ljutina=h[v];
if(leaf)return;
int len=adj[v].size();
for(int i=0;i<len;i++)
{
int cv=adj[v][i].node;
adj[v][i].first.ljutina=dp[cv].ljutina;
adj[v][i].first.brojSecenja=dp[cv].brojSecenja;
}
sort(adj[v].begin(),adj[v].end(),cmp);
/*cout<<v<<" ";
for(auto x:adj[v])
{
cout<<x.first.ljutina<<","<<x.first.brojSecenja<<","<<x.node<<","<<x.par<<" ";
}cout<<endl;*/
int poc=0;if(p!=v)poc=1;
for(int i=poc;i<len;i++)
{
int cv=adj[v][i].node;
dp[v].brojSecenja+=dp[cv].brojSecenja;
if(dp[v].ljutina+dp[cv].ljutina<=k)dp[v].ljutina+=dp[cv].ljutina;
else dp[v].brojSecenja++;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>h[i];
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
adj[x].push_back({{0,0},{y,0}});
adj[y].push_back({{0,0},{x,0}});
}
dfs(1,1);
//for(int i=1;i<=n;i++)cout<<dp[i].ljutina<<","<<dp[i].brojSecenja<<" ";
cout<<dp[1].brojSecenja<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23800 KB |
Output is correct |
2 |
Correct |
25 ms |
23936 KB |
Output is correct |
3 |
Correct |
24 ms |
24016 KB |
Output is correct |
4 |
Correct |
26 ms |
24040 KB |
Output is correct |
5 |
Correct |
26 ms |
24100 KB |
Output is correct |
6 |
Correct |
26 ms |
24100 KB |
Output is correct |
7 |
Correct |
25 ms |
24100 KB |
Output is correct |
8 |
Correct |
26 ms |
24100 KB |
Output is correct |
9 |
Correct |
22 ms |
24100 KB |
Output is correct |
10 |
Correct |
22 ms |
24100 KB |
Output is correct |
11 |
Correct |
24 ms |
24100 KB |
Output is correct |
12 |
Correct |
22 ms |
24100 KB |
Output is correct |
13 |
Correct |
21 ms |
24100 KB |
Output is correct |
14 |
Correct |
21 ms |
24100 KB |
Output is correct |
15 |
Correct |
21 ms |
24100 KB |
Output is correct |
16 |
Correct |
22 ms |
24100 KB |
Output is correct |
17 |
Correct |
21 ms |
24212 KB |
Output is correct |
18 |
Correct |
21 ms |
24212 KB |
Output is correct |
19 |
Correct |
21 ms |
24212 KB |
Output is correct |
20 |
Correct |
26 ms |
24212 KB |
Output is correct |
21 |
Correct |
22 ms |
24212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
41428 KB |
Output is correct |
2 |
Correct |
79 ms |
43424 KB |
Output is correct |
3 |
Correct |
83 ms |
45480 KB |
Output is correct |
4 |
Correct |
79 ms |
47416 KB |
Output is correct |
5 |
Correct |
86 ms |
49412 KB |
Output is correct |
6 |
Correct |
94 ms |
51336 KB |
Output is correct |
7 |
Correct |
81 ms |
53132 KB |
Output is correct |
8 |
Correct |
82 ms |
54668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23800 KB |
Output is correct |
2 |
Correct |
25 ms |
23936 KB |
Output is correct |
3 |
Correct |
24 ms |
24016 KB |
Output is correct |
4 |
Correct |
26 ms |
24040 KB |
Output is correct |
5 |
Correct |
26 ms |
24100 KB |
Output is correct |
6 |
Correct |
26 ms |
24100 KB |
Output is correct |
7 |
Correct |
25 ms |
24100 KB |
Output is correct |
8 |
Correct |
26 ms |
24100 KB |
Output is correct |
9 |
Correct |
22 ms |
24100 KB |
Output is correct |
10 |
Correct |
22 ms |
24100 KB |
Output is correct |
11 |
Correct |
24 ms |
24100 KB |
Output is correct |
12 |
Correct |
22 ms |
24100 KB |
Output is correct |
13 |
Correct |
21 ms |
24100 KB |
Output is correct |
14 |
Correct |
21 ms |
24100 KB |
Output is correct |
15 |
Correct |
21 ms |
24100 KB |
Output is correct |
16 |
Correct |
22 ms |
24100 KB |
Output is correct |
17 |
Correct |
21 ms |
24212 KB |
Output is correct |
18 |
Correct |
21 ms |
24212 KB |
Output is correct |
19 |
Correct |
21 ms |
24212 KB |
Output is correct |
20 |
Correct |
26 ms |
24212 KB |
Output is correct |
21 |
Correct |
22 ms |
24212 KB |
Output is correct |
22 |
Correct |
26 ms |
54668 KB |
Output is correct |
23 |
Correct |
26 ms |
54668 KB |
Output is correct |
24 |
Correct |
26 ms |
54668 KB |
Output is correct |
25 |
Correct |
25 ms |
54668 KB |
Output is correct |
26 |
Correct |
27 ms |
54668 KB |
Output is correct |
27 |
Correct |
26 ms |
54668 KB |
Output is correct |
28 |
Correct |
27 ms |
54668 KB |
Output is correct |
29 |
Correct |
26 ms |
54668 KB |
Output is correct |
30 |
Correct |
22 ms |
54668 KB |
Output is correct |
31 |
Correct |
26 ms |
54668 KB |
Output is correct |
32 |
Correct |
26 ms |
54668 KB |
Output is correct |
33 |
Correct |
26 ms |
54668 KB |
Output is correct |
34 |
Correct |
26 ms |
54668 KB |
Output is correct |
35 |
Correct |
25 ms |
54668 KB |
Output is correct |
36 |
Correct |
25 ms |
54668 KB |
Output is correct |
37 |
Correct |
26 ms |
54668 KB |
Output is correct |
38 |
Runtime error |
54 ms |
63464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
23800 KB |
Output is correct |
2 |
Correct |
25 ms |
23936 KB |
Output is correct |
3 |
Correct |
24 ms |
24016 KB |
Output is correct |
4 |
Correct |
26 ms |
24040 KB |
Output is correct |
5 |
Correct |
26 ms |
24100 KB |
Output is correct |
6 |
Correct |
26 ms |
24100 KB |
Output is correct |
7 |
Correct |
25 ms |
24100 KB |
Output is correct |
8 |
Correct |
26 ms |
24100 KB |
Output is correct |
9 |
Correct |
22 ms |
24100 KB |
Output is correct |
10 |
Correct |
22 ms |
24100 KB |
Output is correct |
11 |
Correct |
24 ms |
24100 KB |
Output is correct |
12 |
Correct |
22 ms |
24100 KB |
Output is correct |
13 |
Correct |
21 ms |
24100 KB |
Output is correct |
14 |
Correct |
21 ms |
24100 KB |
Output is correct |
15 |
Correct |
21 ms |
24100 KB |
Output is correct |
16 |
Correct |
22 ms |
24100 KB |
Output is correct |
17 |
Correct |
21 ms |
24212 KB |
Output is correct |
18 |
Correct |
21 ms |
24212 KB |
Output is correct |
19 |
Correct |
21 ms |
24212 KB |
Output is correct |
20 |
Correct |
26 ms |
24212 KB |
Output is correct |
21 |
Correct |
22 ms |
24212 KB |
Output is correct |
22 |
Correct |
80 ms |
41428 KB |
Output is correct |
23 |
Correct |
79 ms |
43424 KB |
Output is correct |
24 |
Correct |
83 ms |
45480 KB |
Output is correct |
25 |
Correct |
79 ms |
47416 KB |
Output is correct |
26 |
Correct |
86 ms |
49412 KB |
Output is correct |
27 |
Correct |
94 ms |
51336 KB |
Output is correct |
28 |
Correct |
81 ms |
53132 KB |
Output is correct |
29 |
Correct |
82 ms |
54668 KB |
Output is correct |
30 |
Correct |
26 ms |
54668 KB |
Output is correct |
31 |
Correct |
26 ms |
54668 KB |
Output is correct |
32 |
Correct |
26 ms |
54668 KB |
Output is correct |
33 |
Correct |
25 ms |
54668 KB |
Output is correct |
34 |
Correct |
27 ms |
54668 KB |
Output is correct |
35 |
Correct |
26 ms |
54668 KB |
Output is correct |
36 |
Correct |
27 ms |
54668 KB |
Output is correct |
37 |
Correct |
26 ms |
54668 KB |
Output is correct |
38 |
Correct |
22 ms |
54668 KB |
Output is correct |
39 |
Correct |
26 ms |
54668 KB |
Output is correct |
40 |
Correct |
26 ms |
54668 KB |
Output is correct |
41 |
Correct |
26 ms |
54668 KB |
Output is correct |
42 |
Correct |
26 ms |
54668 KB |
Output is correct |
43 |
Correct |
25 ms |
54668 KB |
Output is correct |
44 |
Correct |
25 ms |
54668 KB |
Output is correct |
45 |
Correct |
26 ms |
54668 KB |
Output is correct |
46 |
Runtime error |
54 ms |
63464 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |