| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 630820 |
2022-08-17T07:11:45 Z |
codr0 |
Mergers (JOI19_mergers) |
C++14 |
|
94 ms |
56932 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=1e5+4;
const int K=50+4;
vector<int> adj[N];
int cnt[K];
int t[N][K],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 |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2664 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 24 |
Correct |
2 ms |
2644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2664 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 24 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 26 |
Runtime error |
6 ms |
6720 KB |
Execution killed with signal 11 |
| 27 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2664 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 24 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 26 |
Correct |
64 ms |
29060 KB |
Output is correct |
| 27 |
Correct |
84 ms |
28848 KB |
Output is correct |
| 28 |
Correct |
3 ms |
3400 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 30 |
Correct |
2 ms |
2676 KB |
Output is correct |
| 31 |
Correct |
82 ms |
28808 KB |
Output is correct |
| 32 |
Correct |
3 ms |
3388 KB |
Output is correct |
| 33 |
Correct |
86 ms |
34420 KB |
Output is correct |
| 34 |
Correct |
93 ms |
28748 KB |
Output is correct |
| 35 |
Correct |
3 ms |
3412 KB |
Output is correct |
| 36 |
Correct |
94 ms |
29704 KB |
Output is correct |
| 37 |
Correct |
3 ms |
3404 KB |
Output is correct |
| 38 |
Correct |
4 ms |
3456 KB |
Output is correct |
| 39 |
Correct |
72 ms |
29004 KB |
Output is correct |
| 40 |
Correct |
3 ms |
3668 KB |
Output is correct |
| 41 |
Correct |
65 ms |
28772 KB |
Output is correct |
| 42 |
Correct |
90 ms |
32340 KB |
Output is correct |
| 43 |
Correct |
3 ms |
2676 KB |
Output is correct |
| 44 |
Correct |
88 ms |
33484 KB |
Output is correct |
| 45 |
Correct |
86 ms |
33356 KB |
Output is correct |
| 46 |
Correct |
3 ms |
3396 KB |
Output is correct |
| 47 |
Correct |
3 ms |
3412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
29048 KB |
Output is correct |
| 2 |
Runtime error |
60 ms |
56932 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2664 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 24 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 25 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 26 |
Runtime error |
6 ms |
6720 KB |
Execution killed with signal 11 |
| 27 |
Halted |
0 ms |
0 KB |
- |
