oj.uz

Submission #158159

# Submission time Handle Problem Language Result Execution time Memory
158159 2019-10-15T06:29:47 Z username Mergers (JOI19_mergers) C++14
0 / 100
 275 ms 110148 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];

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)/2<<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:57: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:67:2: note: in expansion of macro 'rep'
  rep(i,0,g[u].size()){
  ^~~
mergers.cpp: At global scope:
mergers.cpp:79: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:92: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:93:3: note: in expansion of macro 'rep'
   rep(j,0,c[i].size())h[c[i][j]]=top;
   ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 102144 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 90 ms 102264 KB Output is correct
5 Incorrect 90 ms 102136 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 102144 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 90 ms 102264 KB Output is correct
5 Incorrect 90 ms 102136 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 102144 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 90 ms 102264 KB Output is correct
5 Incorrect 90 ms 102136 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 110148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 102144 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 90 ms 102264 KB Output is correct
5 Incorrect 90 ms 102136 KB Output isn't correct
6 Halted 0 ms 0 KB -