| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 158156 |
2019-10-15T06:20:35 Z |
username |
Mergers (JOI19_mergers) |
C++14 |
|
309 ms |
114204 KB |
#pragma GCC optimize("O3")
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define tr(it,a) for(auto it:a)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define umin(x,y) (x=min(x,(y)))
#define umax(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
//
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
#define rep(i,j,k) for(int i=(j);i<(k);++i)
#define rrep(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define all(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define __debug
#ifdef __debug
#define ios (void)0
#define pr(...) cerr<<__VA_ARGS__
#define ar(a,s,t) {rep(zy,s,t)pr(a[zy]<<' ');pr(endl);}
#else
#define ios cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
#define pr(...) (void)0
#define ar(...) (void)0
#endif
//
const int maxn=5e5+9,mxlgn=20;
int n,k,cl=0,res=0,s[maxn],h[maxn],in[maxn],ex[maxn],p[mxlgn][maxn];
vector<int>g[maxn],c[maxn];
//struct dsu{
// int fa[maxn],sz[maxn];
// void init(int k){rep(i,0,k)fa[i]=i,sz[i]=1;}
// int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
// void unite(int x,int y){
// x=find(x),y=find(y);
// if(x==y)continue;
// if(sz[x]>sz[y])swap(x,y);
// fa[x]=y,sz[y]+=sz[x];
// }
//}sol;
int isa(int u,int v){return in[u]<=in[v]&&ex[v]<=ex[u];}
int lca(int u,int v){
if(isa(u,v))return u;
else if(isa(v,u))return v;
else{
rrep(i,mxlgn,0)if(p[i][u]>=0&&!isa(p[i][u],v))u=p[i][u];
return p[0][u];
}
}
void dfs1(int u,int f){
p[0][u]=f;
in[u]=cl++;
rep(i,0,g[u].size()){
int v=g[u][i];
if(v==f)continue;
dfs1(v,u);
}
ex[u]=cl;
}
pii dfs2(int u,int f){
int top=h[u],cnt=0;
rep(i,0,g[u].size()){
int v=g[u][i];
if(v==f)continue;
pii tt=dfs2(v,u);
if(isa(tt.f,top))top=tt.f;
cnt+=tt.s;
}
if(!u&&cnt==1)++res;
if(u==top)res+=cnt<1,cnt=1;
return {top,cnt};
}
main(){
ios;
cin>>n>>k;
rep(i,1,n){
int a,b;cin>>a>>b,--a,--b;
g[a].pb(b),g[b].pb(a);
}
rep(i,0,n)cin>>s[i],--s[i],c[s[i]].pb(i);
memset(p,-1,sizeof p);
dfs1(0,-1);
rep(i,0,mxlgn-1)rep(j,0,n)if(p[i][j]>=0)p[i+1][j]=p[i][p[i][j]];
rep(i,0,k){
int top=c[i][0];
rep(j,1,c[i].size())top=lca(top,c[i][j]);
rep(j,0,c[i].size())h[c[i][j]]=top;
}
dfs2(0,-1);
cout<<res-1<<endl;
}
Compilation message
mergers.cpp: In function 'void dfs1(int_fast64_t, int_fast64_t)':
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,j,k) for(int i=(j);i<(k);++i)
^
mergers.cpp:69:2: note: in expansion of macro 'rep'
rep(i,0,g[u].size()){
^~~
mergers.cpp: In function 'pii dfs2(int_fast64_t, int_fast64_t)':
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,j,k) for(int i=(j);i<(k);++i)
^
mergers.cpp:79:2: note: in expansion of macro 'rep'
rep(i,0,g[u].size()){
^~~
mergers.cpp: At global scope:
mergers.cpp:91:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
mergers.cpp: In function 'int main()':
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,j,k) for(int i=(j);i<(k);++i)
^
mergers.cpp:104:3: note: in expansion of macro 'rep'
rep(j,1,c[i].size())top=lca(top,c[i][j]);
^~~
mergers.cpp:21:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,j,k) for(int i=(j);i<(k);++i)
^
mergers.cpp:105:3: note: in expansion of macro 'rep'
rep(j,0,c[i].size())h[c[i][j]]=top;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
102240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
102240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
102240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
261 ms |
111676 KB |
Output is correct |
| 2 |
Incorrect |
309 ms |
114204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
102240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
