| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 339251 |
2020-12-25T00:40:16 Z |
KWang31 |
Mergers (JOI19_mergers) |
Java 11 |
|
650 ms |
35440 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());
}
}
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]; dfs(adj,-1,0);
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+1);
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
Note: mergers.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
9452 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
9452 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
9452 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
650 ms |
35440 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
9452 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
