oj.uz

Submission #138090

# Submission time Handle Problem Language Result Execution time Memory
138090 2019-07-29T10:12:26 Z MohamedAhmed04 Mergers (JOI19_mergers) C++14
0 / 100
 139 ms 50812 KB 
    #include <bits/stdc++.h>
     
    using namespace std ;
     
    const int MAX = 5e5 + 5 ;
     
    vector< vector<int> >adj(MAX) ;
    vector< vector<int> >st(MAX) ;
    vector< vector<int> >level(MAX) ;
    int n , k;
     
    int state[MAX] , P[MAX][22] , depth[MAX] , lca[MAX];
    int lowestdepth[MAX] , nodenum[MAX] , deg[MAX] , id[MAX];
    int nodes = 0 ;
     
    void dfs(int node , int lvl , int par)
    {
    	depth[node] = lvl ;
    	P[node][0] = par ;
    	for(auto &child : adj[node])
    	{
    		if(child == par)
    			continue ;
    		dfs(child , lvl + 1 , node) ;
    	}
    	return ;
    }
     
    void preprocess()
    {
    	dfs(1 , 0 , 0) ;
    	for(int j = 1 ; j < 22 ; ++j)
    	{
    		for(int i = 1 ; i <= n ; ++i)
    			P[i][j] = P[P[i][j-1]][j-1] ;
    	}
    	return ;
    }
     
    int LCA(int x , int y)
    {
    	if(depth[x] < depth[y])
    		swap(x , y) ;
    	for(int i = 21 ; i >= 0 ; --i)
    	{
    		if(depth[x] - (1 << i) >= depth[y])
    			x = P[x][i] ;
    	}
    	if(x == y)
    		return x ;
    	for(int i = 21 ; i >= 0 ; --i)
    	{
    		if(P[x][i] != P[y][i])
    			x = P[x][i] , y = P[y][i] ;
    	}
    	return P[x][0] ;
    }
     
    int main()
    {
    	ios_base::sync_with_stdio(0) ;
    	cin.tie(0) ;
    	cin>>n>>k ;
    	for(int i = 0 ; i < n-1 ; ++i)
    	{
    		int x , y ;
    		cin>>x>>y ;
    		adj[x].push_back(y) ;
    		adj[y].push_back(x) ;
    	}
    	for(int i = 1 ; i <= n ; ++i)
    	{
    		cin>>state[i] ;
    		st[state[i]].push_back(i) ;
    	}
    	preprocess() ;
    	for(int i = 1 ; i <= k ; ++i)
    	{
    		int lca2 = st[i][0] ;
    		for(auto &node : st[i])
    			lca2 = LCA(lca2 , node) ;
    		lca2 = P[lca2][0] ;
    		for(auto &node : st[i])
    		{
    			lca[node] = lca2 ;
    		}
    	}
    	int maxdepth = 0 ;
    	for(int i = 1 ; i <= n ; ++i)
    	{
    		level[depth[i]].push_back(i) ;
    		maxdepth = max(maxdepth , depth[i]) ;
    		lowestdepth[i] = 1e9 ;
    	}
    	depth[0] = -1 ;
    	for(int i = maxdepth ; i >= 0 ; --i)
    	{
    		for(auto &node : level[i])
    		{
    			if(id[state[node]] == 0)
    			{
    				nodes++ ;
    				id[state[node]] = nodes;
    			}
    			nodenum[node] = id[state[node]] ;
    			//cout<<node<<" : "<<nodenum[node]<<"\n";
    			lowestdepth[node] = min(lowestdepth[node] , depth[lca[node]]) ;
    			if(i == 0)
    				continue;
    			if(i-1 == lowestdepth[node])
    			{
    				if(id[state[P[node][0]]] == 0)
    				{
    					nodes++ ;
    					id[state[P[node][0]]] = nodes ;
    					nodenum[P[node][0]] = id[state[P[node][0]]] ;
    				}
    				deg[nodenum[P[node][0]]]++ ;
    				deg[nodenum[node]]++ ;
    			}
    			else
    			{
    				if(id[state[P[node][0]]] == 0)
    				{
    					id[state[P[node][0]]] = id[state[node]] ;
    					nodenum[P[node][0]] = nodenum[node] ; 
    				}
    				lowestdepth[P[node][0]] = lowestdepth[node] ;
    				nodenum[P[node][0]] = nodenum[node] ;
    			}
    		}
    	}
    	int cnt = 0 ;
    	for(int i = 1 ; i <= n ; ++i)
    	{
    		if(deg[i] == 1)
    			cnt++ ;
    	}
    	return cout<<(cnt+1)/2<<"\n" , 0 ;
    }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35604 KB Output is correct
4 Correct 35 ms 35656 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35704 KB Output is correct
8 Incorrect 34 ms 35704 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35604 KB Output is correct
4 Correct 35 ms 35656 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35704 KB Output is correct
8 Incorrect 34 ms 35704 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35604 KB Output is correct
4 Correct 35 ms 35656 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35704 KB Output is correct
8 Incorrect 34 ms 35704 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 35 ms 35576 KB Output is correct
3 Correct 35 ms 35604 KB Output is correct
4 Correct 35 ms 35656 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 34 ms 35576 KB Output is correct
7 Correct 34 ms 35704 KB Output is correct
8 Incorrect 34 ms 35704 KB Output isn't correct
9 Halted 0 ms 0 KB -