oj.uz

Submission #158158

# Submission time Handle Problem Language Result Execution time Memory
158158 2019-10-15T06:27:59 Z username Mergers (JOI19_mergers) C++14
0 / 100
 295 ms 112240 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/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 90 ms 102136 KB Output is correct
2 Correct 91 ms 102128 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 91 ms 102116 KB Output is correct
5 Correct 90 ms 102140 KB Output is correct
6 Correct 91 ms 102264 KB Output is correct
7 Correct 90 ms 102136 KB Output is correct
8 Correct 90 ms 102164 KB Output is correct
9 Correct 90 ms 102136 KB Output is correct
10 Correct 98 ms 102328 KB Output is correct
11 Correct 90 ms 102136 KB Output is correct
12 Correct 91 ms 102136 KB Output is correct
13 Correct 90 ms 102264 KB Output is correct
14 Incorrect 90 ms 102136 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 102136 KB Output is correct
2 Correct 91 ms 102128 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 91 ms 102116 KB Output is correct
5 Correct 90 ms 102140 KB Output is correct
6 Correct 91 ms 102264 KB Output is correct
7 Correct 90 ms 102136 KB Output is correct
8 Correct 90 ms 102164 KB Output is correct
9 Correct 90 ms 102136 KB Output is correct
10 Correct 98 ms 102328 KB Output is correct
11 Correct 90 ms 102136 KB Output is correct
12 Correct 91 ms 102136 KB Output is correct
13 Correct 90 ms 102264 KB Output is correct
14 Incorrect 90 ms 102136 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 102136 KB Output is correct
2 Correct 91 ms 102128 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 91 ms 102116 KB Output is correct
5 Correct 90 ms 102140 KB Output is correct
6 Correct 91 ms 102264 KB Output is correct
7 Correct 90 ms 102136 KB Output is correct
8 Correct 90 ms 102164 KB Output is correct
9 Correct 90 ms 102136 KB Output is correct
10 Correct 98 ms 102328 KB Output is correct
11 Correct 90 ms 102136 KB Output is correct
12 Correct 91 ms 102136 KB Output is correct
13 Correct 90 ms 102264 KB Output is correct
14 Incorrect 90 ms 102136 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 110156 KB Output is correct
2 Incorrect 295 ms 112240 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 102136 KB Output is correct
2 Correct 91 ms 102128 KB Output is correct
3 Correct 90 ms 102136 KB Output is correct
4 Correct 91 ms 102116 KB Output is correct
5 Correct 90 ms 102140 KB Output is correct
6 Correct 91 ms 102264 KB Output is correct
7 Correct 90 ms 102136 KB Output is correct
8 Correct 90 ms 102164 KB Output is correct
9 Correct 90 ms 102136 KB Output is correct
10 Correct 98 ms 102328 KB Output is correct
11 Correct 90 ms 102136 KB Output is correct
12 Correct 91 ms 102136 KB Output is correct
13 Correct 90 ms 102264 KB Output is correct
14 Incorrect 90 ms 102136 KB Output isn't correct
15 Halted 0 ms 0 KB -