| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 630819 |
2022-08-17T07:10:18 Z |
codr0 |
Mergers (JOI19_mergers) |
C++14 |
|
48 ms |
35936 KB |
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define err(x) cerr<<#x<<" : "<<x<<'\n';
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1
#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
using namespace std;
const int N=3000+4;
vector<int> adj[N];
int cnt[N];
int t[N][N],dp[N];
int n,k;
void dfs(int v,int p){
for(int u:adj[v]) if(u!=p){
dfs(u,v);
dp[v]+=dp[u];
FOR(j,1,k) t[v][j]+=t[u][j];
}
if(dp[v]==0&&v!=p){
dp[v]=1;
FOR(j,1,k) if(t[v][j]!=cnt[j]&&t[v][j]!=0) dp[v]=0;
}
}
int main(){
iostream::sync_with_stdio(0); cin.tie(0);
cin>>n>>k;
FOR(_,1,n-1){
int u,v; cin>>u>>v;
adj[u].pb(v);
adj[v].pb(u);
}
if(n<=2){
int w0,w1; cin>>w0;
if(n==1){
cout<<"0\n";
return 0;
}
if(n==2){
cin>>w1;
cout<<(w0!=w1)<<'\n';
return 0;
}
assert(1==2);
}
FOR(i,1,n){
int w; cin>>w;
t[i][w]++;
cnt[w]++;
}
int root=1;
FOR(i,1,n) if(SZ(adj[i])>1) root=i;
dfs(root,root);
FOR(i,1,n) if(i!=root){
bool ok=1;
FOR(j,1,k) if(t[i][j]!=cnt[j]&&t[i][j]!=0) ok=0;
if(ok==0) continue;
if(dp[i]==dp[root]) dp[root]++;
}
cout<<(dp[root]/2+(dp[root]&1))<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
724 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
724 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
724 KB |
Output is correct |
| 22 |
Correct |
1 ms |
724 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
724 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
724 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
724 KB |
Output is correct |
| 22 |
Correct |
1 ms |
724 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
596 KB |
Output is correct |
| 26 |
Correct |
33 ms |
27960 KB |
Output is correct |
| 27 |
Correct |
7 ms |
13080 KB |
Output is correct |
| 28 |
Correct |
48 ms |
26180 KB |
Output is correct |
| 29 |
Correct |
30 ms |
26004 KB |
Output is correct |
| 30 |
Correct |
10 ms |
13680 KB |
Output is correct |
| 31 |
Correct |
1 ms |
596 KB |
Output is correct |
| 32 |
Correct |
46 ms |
35936 KB |
Output is correct |
| 33 |
Correct |
1 ms |
604 KB |
Output is correct |
| 34 |
Correct |
8 ms |
12500 KB |
Output is correct |
| 35 |
Correct |
31 ms |
26156 KB |
Output is correct |
| 36 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 37 |
Correct |
22 ms |
21196 KB |
Output is correct |
| 38 |
Correct |
1 ms |
724 KB |
Output is correct |
| 39 |
Correct |
23 ms |
21376 KB |
Output is correct |
| 40 |
Correct |
6 ms |
12568 KB |
Output is correct |
| 41 |
Correct |
6 ms |
12636 KB |
Output is correct |
| 42 |
Correct |
19 ms |
12636 KB |
Output is correct |
| 43 |
Correct |
7 ms |
12772 KB |
Output is correct |
| 44 |
Correct |
1 ms |
780 KB |
Output is correct |
| 45 |
Correct |
33 ms |
35684 KB |
Output is correct |
| 46 |
Correct |
21 ms |
21588 KB |
Output is correct |
| 47 |
Correct |
1 ms |
724 KB |
Output is correct |
| 48 |
Correct |
15 ms |
16716 KB |
Output is correct |
| 49 |
Correct |
32 ms |
12380 KB |
Output is correct |
| 50 |
Correct |
40 ms |
26196 KB |
Output is correct |
| 51 |
Correct |
12 ms |
18388 KB |
Output is correct |
| 52 |
Correct |
6 ms |
12568 KB |
Output is correct |
| 53 |
Correct |
19 ms |
12628 KB |
Output is correct |
| 54 |
Correct |
8 ms |
12916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
724 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
724 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
724 KB |
Output is correct |
| 22 |
Correct |
1 ms |
724 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
600 KB |
Output is correct |
| 26 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 27 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| 3 |
Correct |
1 ms |
724 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
724 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
724 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
724 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
724 KB |
Output is correct |
| 22 |
Correct |
1 ms |
724 KB |
Output is correct |
| 23 |
Correct |
1 ms |
340 KB |
Output is correct |
| 24 |
Correct |
1 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
596 KB |
Output is correct |
| 26 |
Correct |
33 ms |
27960 KB |
Output is correct |
| 27 |
Correct |
7 ms |
13080 KB |
Output is correct |
| 28 |
Correct |
48 ms |
26180 KB |
Output is correct |
| 29 |
Correct |
30 ms |
26004 KB |
Output is correct |
| 30 |
Correct |
10 ms |
13680 KB |
Output is correct |
| 31 |
Correct |
1 ms |
596 KB |
Output is correct |
| 32 |
Correct |
46 ms |
35936 KB |
Output is correct |
| 33 |
Correct |
1 ms |
604 KB |
Output is correct |
| 34 |
Correct |
8 ms |
12500 KB |
Output is correct |
| 35 |
Correct |
31 ms |
26156 KB |
Output is correct |
| 36 |
Correct |
7 ms |
12756 KB |
Output is correct |
| 37 |
Correct |
22 ms |
21196 KB |
Output is correct |
| 38 |
Correct |
1 ms |
724 KB |
Output is correct |
| 39 |
Correct |
23 ms |
21376 KB |
Output is correct |
| 40 |
Correct |
6 ms |
12568 KB |
Output is correct |
| 41 |
Correct |
6 ms |
12636 KB |
Output is correct |
| 42 |
Correct |
19 ms |
12636 KB |
Output is correct |
| 43 |
Correct |
7 ms |
12772 KB |
Output is correct |
| 44 |
Correct |
1 ms |
780 KB |
Output is correct |
| 45 |
Correct |
33 ms |
35684 KB |
Output is correct |
| 46 |
Correct |
21 ms |
21588 KB |
Output is correct |
| 47 |
Correct |
1 ms |
724 KB |
Output is correct |
| 48 |
Correct |
15 ms |
16716 KB |
Output is correct |
| 49 |
Correct |
32 ms |
12380 KB |
Output is correct |
| 50 |
Correct |
40 ms |
26196 KB |
Output is correct |
| 51 |
Correct |
12 ms |
18388 KB |
Output is correct |
| 52 |
Correct |
6 ms |
12568 KB |
Output is correct |
| 53 |
Correct |
19 ms |
12628 KB |
Output is correct |
| 54 |
Correct |
8 ms |
12916 KB |
Output is correct |
| 55 |
Correct |
1 ms |
600 KB |
Output is correct |
| 56 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
| 57 |
Halted |
0 ms |
0 KB |
- |
