oj.uz

Submission #339248

# Submission time Handle Problem Language Result Execution time Memory
339248 2020-12-25T00:30:32 Z KWang31 Mergers (JOI19_mergers) Java 11
56 / 100
 3000 ms 50412 KB 
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()); 
        } 
  
        
    } 
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=998244353;
    static int[] rk, p,siz;
    static int[] par,dep;
    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]; dfs(adj,-1,0);
        
        int[] skip=new int[N];//Skipping: avoiding repeated merging
        for (int i = 0; i < N; i++) {
            skip[i]=i;
        }
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < states[i].size()-1; j++) {
                a=states[i].get(j); b=states[i].get(j+1);
                
                while(a!=b){
                    if(dep[a]>=dep[b]){
                        skip[a]=find(par[a],skip); a=par[a]; 
                    }else{
                        skip[b]=find(par[b],skip); b=par[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,skip);
            for (int j : adj[i]) {
                if(a!=find(j,skip)){
                    //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, int[] p){
        if(p[x]==x)return x;
        p[x]=find(p[x],p); return p[x];
    }
    
    public static void merge(int a, int b) {
        if(rk[a]<rk[b]) {
            p[a]=b; siz[b]+=siz[a];
        }else if(rk[a]==rk[b]) {
            p[a]=b; rk[b]++;siz[b]+=siz[a];
        }else {
            p[b]=a; siz[a]+=siz[b];
        }
    }
    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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 78 ms 8684 KB Output is correct
3 Correct 78 ms 8556 KB Output is correct
4 Correct 71 ms 8556 KB Output is correct
5 Correct 71 ms 8556 KB Output is correct
6 Correct 76 ms 8556 KB Output is correct
7 Correct 72 ms 8636 KB Output is correct
8 Correct 78 ms 8428 KB Output is correct
9 Correct 76 ms 8520 KB Output is correct
10 Correct 73 ms 8540 KB Output is correct
11 Correct 78 ms 8556 KB Output is correct
12 Correct 77 ms 8556 KB Output is correct
13 Correct 72 ms 8684 KB Output is correct
14 Correct 77 ms 8684 KB Output is correct
15 Correct 80 ms 8556 KB Output is correct
16 Correct 70 ms 8556 KB Output is correct
17 Correct 70 ms 8556 KB Output is correct
18 Correct 77 ms 8556 KB Output is correct
19 Correct 70 ms 8684 KB Output is correct
20 Correct 70 ms 8556 KB Output is correct
21 Correct 77 ms 8556 KB Output is correct
22 Correct 80 ms 8528 KB Output is correct
23 Correct 72 ms 8472 KB Output is correct
24 Correct 72 ms 8684 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 78 ms 8684 KB Output is correct
3 Correct 78 ms 8556 KB Output is correct
4 Correct 71 ms 8556 KB Output is correct
5 Correct 71 ms 8556 KB Output is correct
6 Correct 76 ms 8556 KB Output is correct
7 Correct 72 ms 8636 KB Output is correct
8 Correct 78 ms 8428 KB Output is correct
9 Correct 76 ms 8520 KB Output is correct
10 Correct 73 ms 8540 KB Output is correct
11 Correct 78 ms 8556 KB Output is correct
12 Correct 77 ms 8556 KB Output is correct
13 Correct 72 ms 8684 KB Output is correct
14 Correct 77 ms 8684 KB Output is correct
15 Correct 80 ms 8556 KB Output is correct
16 Correct 70 ms 8556 KB Output is correct
17 Correct 70 ms 8556 KB Output is correct
18 Correct 77 ms 8556 KB Output is correct
19 Correct 70 ms 8684 KB Output is correct
20 Correct 70 ms 8556 KB Output is correct
21 Correct 77 ms 8556 KB Output is correct
22 Correct 80 ms 8528 KB Output is correct
23 Correct 72 ms 8472 KB Output is correct
24 Correct 72 ms 8684 KB Output is correct
25 Correct 74 ms 8556 KB Output is correct
26 Correct 289 ms 14660 KB Output is correct
27 Correct 309 ms 14692 KB Output is correct
28 Correct 289 ms 14940 KB Output is correct
29 Correct 288 ms 14748 KB Output is correct
30 Correct 305 ms 14432 KB Output is correct
31 Correct 75 ms 8556 KB Output is correct
32 Correct 292 ms 15000 KB Output is correct
33 Correct 73 ms 8556 KB Output is correct
34 Correct 283 ms 14560 KB Output is correct
35 Correct 286 ms 14688 KB Output is correct
36 Correct 287 ms 14688 KB Output is correct
37 Correct 296 ms 14652 KB Output is correct
38 Correct 77 ms 8552 KB Output is correct
39 Correct 322 ms 14808 KB Output is correct
40 Correct 353 ms 14564 KB Output is correct
41 Correct 313 ms 14816 KB Output is correct
42 Correct 291 ms 14744 KB Output is correct
43 Correct 358 ms 15196 KB Output is correct
44 Correct 78 ms 8556 KB Output is correct
45 Correct 342 ms 14688 KB Output is correct
46 Correct 357 ms 14636 KB Output is correct
47 Correct 78 ms 8556 KB Output is correct
48 Correct 288 ms 14564 KB Output is correct
49 Correct 286 ms 14828 KB Output is correct
50 Correct 287 ms 14928 KB Output is correct
51 Correct 290 ms 14672 KB Output is correct
52 Correct 284 ms 14532 KB Output is correct
53 Correct 291 ms 14732 KB Output is correct
54 Correct 311 ms 14816 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 78 ms 8684 KB Output is correct
3 Correct 78 ms 8556 KB Output is correct
4 Correct 71 ms 8556 KB Output is correct
5 Correct 71 ms 8556 KB Output is correct
6 Correct 76 ms 8556 KB Output is correct
7 Correct 72 ms 8636 KB Output is correct
8 Correct 78 ms 8428 KB Output is correct
9 Correct 76 ms 8520 KB Output is correct
10 Correct 73 ms 8540 KB Output is correct
11 Correct 78 ms 8556 KB Output is correct
12 Correct 77 ms 8556 KB Output is correct
13 Correct 72 ms 8684 KB Output is correct
14 Correct 77 ms 8684 KB Output is correct
15 Correct 80 ms 8556 KB Output is correct
16 Correct 70 ms 8556 KB Output is correct
17 Correct 70 ms 8556 KB Output is correct
18 Correct 77 ms 8556 KB Output is correct
19 Correct 70 ms 8684 KB Output is correct
20 Correct 70 ms 8556 KB Output is correct
21 Correct 77 ms 8556 KB Output is correct
22 Correct 80 ms 8528 KB Output is correct
23 Correct 72 ms 8472 KB Output is correct
24 Correct 72 ms 8684 KB Output is correct
25 Correct 73 ms 8428 KB Output is correct
26 Correct 712 ms 35040 KB Output is correct
27 Correct 750 ms 35300 KB Output is correct
28 Correct 322 ms 14696 KB Output is correct
29 Correct 73 ms 8556 KB Output is correct
30 Correct 74 ms 8556 KB Output is correct
31 Correct 750 ms 35244 KB Output is correct
32 Correct 300 ms 14576 KB Output is correct
33 Execution timed out 3070 ms 38372 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 34884 KB Output is correct
2 Correct 760 ms 48376 KB Output is correct
3 Correct 288 ms 14688 KB Output is correct
4 Correct 336 ms 14708 KB Output is correct
5 Correct 85 ms 8556 KB Output is correct
6 Correct 74 ms 8556 KB Output is correct
7 Correct 294 ms 14540 KB Output is correct
8 Correct 768 ms 37040 KB Output is correct
9 Correct 289 ms 14700 KB Output is correct
10 Correct 741 ms 35148 KB Output is correct
11 Correct 77 ms 8528 KB Output is correct
12 Correct 787 ms 35412 KB Output is correct
13 Correct 763 ms 37216 KB Output is correct
14 Correct 828 ms 41780 KB Output is correct
15 Correct 695 ms 35612 KB Output is correct
16 Correct 293 ms 14840 KB Output is correct
17 Correct 79 ms 8684 KB Output is correct
18 Correct 751 ms 46948 KB Output is correct
19 Correct 1204 ms 50412 KB Output is correct
20 Correct 341 ms 14640 KB Output is correct
21 Correct 79 ms 8540 KB Output is correct
22 Correct 758 ms 39808 KB Output is correct
23 Correct 289 ms 14508 KB Output is correct
24 Correct 736 ms 35748 KB Output is correct
25 Correct 772 ms 43980 KB Output is correct
26 Correct 285 ms 14688 KB Output is correct
27 Correct 285 ms 14800 KB Output is correct
28 Correct 285 ms 14560 KB Output is correct
29 Correct 288 ms 14460 KB Output is correct
30 Correct 288 ms 14776 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 8556 KB Output is correct
2 Correct 78 ms 8684 KB Output is correct
3 Correct 78 ms 8556 KB Output is correct
4 Correct 71 ms 8556 KB Output is correct
5 Correct 71 ms 8556 KB Output is correct
6 Correct 76 ms 8556 KB Output is correct
7 Correct 72 ms 8636 KB Output is correct
8 Correct 78 ms 8428 KB Output is correct
9 Correct 76 ms 8520 KB Output is correct
10 Correct 73 ms 8540 KB Output is correct
11 Correct 78 ms 8556 KB Output is correct
12 Correct 77 ms 8556 KB Output is correct
13 Correct 72 ms 8684 KB Output is correct
14 Correct 77 ms 8684 KB Output is correct
15 Correct 80 ms 8556 KB Output is correct
16 Correct 70 ms 8556 KB Output is correct
17 Correct 70 ms 8556 KB Output is correct
18 Correct 77 ms 8556 KB Output is correct
19 Correct 70 ms 8684 KB Output is correct
20 Correct 70 ms 8556 KB Output is correct
21 Correct 77 ms 8556 KB Output is correct
22 Correct 80 ms 8528 KB Output is correct
23 Correct 72 ms 8472 KB Output is correct
24 Correct 72 ms 8684 KB Output is correct
25 Correct 74 ms 8556 KB Output is correct
26 Correct 289 ms 14660 KB Output is correct
27 Correct 309 ms 14692 KB Output is correct
28 Correct 289 ms 14940 KB Output is correct
29 Correct 288 ms 14748 KB Output is correct
30 Correct 305 ms 14432 KB Output is correct
31 Correct 75 ms 8556 KB Output is correct
32 Correct 292 ms 15000 KB Output is correct
33 Correct 73 ms 8556 KB Output is correct
34 Correct 283 ms 14560 KB Output is correct
35 Correct 286 ms 14688 KB Output is correct
36 Correct 287 ms 14688 KB Output is correct
37 Correct 296 ms 14652 KB Output is correct
38 Correct 77 ms 8552 KB Output is correct
39 Correct 322 ms 14808 KB Output is correct
40 Correct 353 ms 14564 KB Output is correct
41 Correct 313 ms 14816 KB Output is correct
42 Correct 291 ms 14744 KB Output is correct
43 Correct 358 ms 15196 KB Output is correct
44 Correct 78 ms 8556 KB Output is correct
45 Correct 342 ms 14688 KB Output is correct
46 Correct 357 ms 14636 KB Output is correct
47 Correct 78 ms 8556 KB Output is correct
48 Correct 288 ms 14564 KB Output is correct
49 Correct 286 ms 14828 KB Output is correct
50 Correct 287 ms 14928 KB Output is correct
51 Correct 290 ms 14672 KB Output is correct
52 Correct 284 ms 14532 KB Output is correct
53 Correct 291 ms 14732 KB Output is correct
54 Correct 311 ms 14816 KB Output is correct
55 Correct 73 ms 8428 KB Output is correct
56 Correct 712 ms 35040 KB Output is correct
57 Correct 750 ms 35300 KB Output is correct
58 Correct 322 ms 14696 KB Output is correct
59 Correct 73 ms 8556 KB Output is correct
60 Correct 74 ms 8556 KB Output is correct
61 Correct 750 ms 35244 KB Output is correct
62 Correct 300 ms 14576 KB Output is correct
63 Execution timed out 3070 ms 38372 KB Time limit exceeded
64 Halted 0 ms 0 KB -