Submission #339254

#	Time	Username	Problem	Language	Result	Execution time	Memory
339254		KWang31	Mergers (JOI19_mergers)	Java	100 / 100	2775 ms	201412 KiB

mergers

import java.io.*; import java.util.*;
public class mergers{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    
    static int MOD=998244353;
    
    static int[] par,dep;
    static int[] skip;
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int M=br.nextInt();
        ArrayList<Integer> states[]=new ArrayList[M]; for(int i=0;i<M;i++){states[i]=new ArrayList<>();}
        ArrayList<Integer> adj[]=new ArrayList[N]; for(int i=0;i<N;i++){adj[i]=new ArrayList<>();}
        int a,b;
        for (int i = 0; i < N-1; i++) {
            a=br.nextInt()-1; b=br.nextInt()-1; adj[a].add(b); adj[b].add(a);
        }
        for (int i = 0; i < N; i++) {
            a=br.nextInt()-1; states[a].add(i);
        }
        par=new int[N]; dep=new int[N]; 
        Queue<Integer> qu=new LinkedList<>(); qu.add(0);
        while(!qu.isEmpty()){
            int p=qu.poll();
            for (int i : adj[p]) {
                if(i==par[p])continue;
                par[i]=p; dep[i]=dep[p]+1; qu.add(i);
            }
        }
        
        skip=new int[N];//Skipping: avoiding repeated merging
        for (int i = 0; i < N; i++) {
            skip[i]=i;
        }
        int u;
        for (int i = 0; i < M; i++) {
            if(states[i].isEmpty())continue;
            u=states[i].get(0);
            for (int j = 1; j < states[i].size(); j++) {
                a=u; b=states[i].get(j);
                
                while(a!=b){
                    if(dep[a]>=dep[b]){
                        skip[a]=find(par[a]); a=skip[a]; 
                    }else{
                        skip[b]=find(par[b]); b=skip[b]; 
                    }
                }
                //For each a, we have merged a with its 1st, .., kth ancestor.
                //They belong to the same state
            }
        }
        //In the end, all vertices of the same state have the same skip
        //Therefore, after merging, if two vertices don't have some skip, they are not in the same state
        int[] deg=new int[N];
        
        for (int i = 0; i < N; i++) {
            a=find(i);
            for (int j : adj[i]) {
                if(a!=find(j)){
                    //Notice in the compressed form, there is only one leader for each state, namely j
                    //If i is adjacent to two vertices with same find, i must have that find too
                    deg[a]++;
                }
            }
        }
        //System.out.println(Arrays.toString(deg));
        int ans=0;
        for (int i = 0; i < N; i++) {
            if(deg[i]==1)ans++;
        }
        System.out.println((ans+1)/2);
        //If a state is a leaf, there exist exactly one 
    }
    
    public static int find(int x){
        if(skip[x]==x)return x;
        skip[x]=find(skip[x]); return skip[x];
    }
    /*
    public static void dfs(ArrayList<Integer>[] adj, int p, int v){
        for (int c : adj[v]) {
            if(c==p)continue;
            dep[c]=dep[v]+1; par[c]=v; dfs(adj,v,c);
        }
    }*/
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

Compilation message (stderr)

Note: mergers.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30