| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 630809 |
2022-08-17T06:55:51 Z |
codr0 |
Mergers (JOI19_mergers) |
C++14 |
|
29 ms |
35972 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);
cout<<(dp[root]/2+(dp[root]&1))<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
784 KB |
Output is correct |
| 3 |
Correct |
1 ms |
784 KB |
Output is correct |
| 4 |
Correct |
1 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 |
400 KB |
Output is correct |
| 11 |
Correct |
1 ms |
784 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
1 ms |
392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
404 KB |
Output is correct |
| 18 |
Correct |
1 ms |
788 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 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 |
400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
784 KB |
Output is correct |
| 3 |
Correct |
1 ms |
784 KB |
Output is correct |
| 4 |
Correct |
1 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 |
400 KB |
Output is correct |
| 11 |
Correct |
1 ms |
784 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
1 ms |
392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
404 KB |
Output is correct |
| 18 |
Correct |
1 ms |
788 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 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 |
400 KB |
Output is correct |
| 25 |
Correct |
1 ms |
596 KB |
Output is correct |
| 26 |
Correct |
25 ms |
27904 KB |
Output is correct |
| 27 |
Correct |
9 ms |
13140 KB |
Output is correct |
| 28 |
Correct |
22 ms |
26212 KB |
Output is correct |
| 29 |
Correct |
22 ms |
26060 KB |
Output is correct |
| 30 |
Correct |
8 ms |
13736 KB |
Output is correct |
| 31 |
Correct |
1 ms |
596 KB |
Output is correct |
| 32 |
Correct |
21 ms |
35972 KB |
Output is correct |
| 33 |
Correct |
1 ms |
596 KB |
Output is correct |
| 34 |
Correct |
7 ms |
12580 KB |
Output is correct |
| 35 |
Correct |
29 ms |
26156 KB |
Output is correct |
| 36 |
Incorrect |
7 ms |
12828 KB |
Output isn't correct |
| 37 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
784 KB |
Output is correct |
| 3 |
Correct |
1 ms |
784 KB |
Output is correct |
| 4 |
Correct |
1 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 |
400 KB |
Output is correct |
| 11 |
Correct |
1 ms |
784 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
1 ms |
392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
404 KB |
Output is correct |
| 18 |
Correct |
1 ms |
788 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 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 |
400 KB |
Output is correct |
| 25 |
Correct |
1 ms |
596 KB |
Output is correct |
| 26 |
Runtime error |
1 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 |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
784 KB |
Output is correct |
| 3 |
Correct |
1 ms |
784 KB |
Output is correct |
| 4 |
Correct |
1 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 |
400 KB |
Output is correct |
| 11 |
Correct |
1 ms |
784 KB |
Output is correct |
| 12 |
Correct |
1 ms |
724 KB |
Output is correct |
| 13 |
Correct |
1 ms |
392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
724 KB |
Output is correct |
| 15 |
Correct |
1 ms |
724 KB |
Output is correct |
| 16 |
Correct |
0 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
404 KB |
Output is correct |
| 18 |
Correct |
1 ms |
788 KB |
Output is correct |
| 19 |
Correct |
1 ms |
340 KB |
Output is correct |
| 20 |
Correct |
1 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 |
400 KB |
Output is correct |
| 25 |
Correct |
1 ms |
596 KB |
Output is correct |
| 26 |
Correct |
25 ms |
27904 KB |
Output is correct |
| 27 |
Correct |
9 ms |
13140 KB |
Output is correct |
| 28 |
Correct |
22 ms |
26212 KB |
Output is correct |
| 29 |
Correct |
22 ms |
26060 KB |
Output is correct |
| 30 |
Correct |
8 ms |
13736 KB |
Output is correct |
| 31 |
Correct |
1 ms |
596 KB |
Output is correct |
| 32 |
Correct |
21 ms |
35972 KB |
Output is correct |
| 33 |
Correct |
1 ms |
596 KB |
Output is correct |
| 34 |
Correct |
7 ms |
12580 KB |
Output is correct |
| 35 |
Correct |
29 ms |
26156 KB |
Output is correct |
| 36 |
Incorrect |
7 ms |
12828 KB |
Output isn't correct |
| 37 |
Halted |
0 ms |
0 KB |
- |
