Submission #140115

#	Time	Username	Problem	Language	Result	Execution time	Memory
140115		KLPP	Mergers (JOI19_mergers)	C++14	100 / 100	1219 ms	146124 KiB

mergers

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define INF 1000000000000000000
int n,k;
vector<int> nei[1000000];
int state[1000000];
vector<int> states[1000000];
int dfs_num[1000000];
int dfs_low[1000000];
stack<int> s;
int parent[1000000];
int counter;
int SCC_count;
int SCC[1000000];
int deg[1000000];
bool visited[1000000];
int parent_tree[1000000];
void DFS(int node){
  dfs_num[node]=counter;
  dfs_low[node]=counter;
  counter++;
  s.push(node);
  visited[node]=true;
  trav(a,nei[node]){
    if(dfs_num[a]==-1){
      parent[a]=node;
      DFS(a);
      dfs_low[node]=min(dfs_low[node],dfs_low[a]);
    }else{
      if(parent[node]!=a && visited[a]){
	dfs_low[node]=min(dfs_low[node],dfs_num[a]);
      }
    }
  }
  if(dfs_low[node]==dfs_num[node]){
    while(true){
      int u=s.top();
      s.pop();
      visited[u]=false;
      SCC[u]=SCC_count;
      dfs_num[u]=-1;
      if(u==node){
	SCC_count++;
	return;
      }
    }
  }
}
void DFS2(int node){
  visited[node]=true;
  trav(a,nei[node]){
    if(!visited[a]){
      parent_tree[a]=node;
      DFS2(a);
    }
  }
}
class DSU{
  int parent[1000000];
  int size[1000000];
public:
  void init(int K){
    rep(i,0,K){
      parent[i]=i;
      size[i]=1;
    }
  }
  int root(int node){
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
  }
  void merge(int a, int b){
    a=root(a);
    b=root(b);
    if(a==b)return;
    if(size[a]<size[b])swap(a,b);
    size[a]+=size[b];
    parent[b]=a;
  }
};
int main(){
  scanf("%d %d",&n,&k);
  rep(i,0,n)visited[i]=false;
  vector<pii> edges;
  rep(i,0,n-1){
    int x,y;
    scanf("%d %d",&x,&y);
    x--;y--;
    nei[x].push_back(y);
    nei[y].push_back(x);
    edges.push_back(pii(x,y));
    edges.push_back(pii(y,x));
  }
  DFS2(0);
  rep(i,0,n){
    scanf("%d",&state[i]);
    state[i]--;
    states[state[i]].push_back(i);
  }
  rep(i,0,k){
    rep(j,0,states[i].size()-1){
      pii new_edge=pii(states[i][j],states[i][j+1]);
      if(parent_tree[new_edge.first]!=new_edge.second && parent_tree[new_edge.second]!=new_edge.first){
	nei[states[i][j]].push_back(states[i][j+1]);
	nei[states[i][j+1]].push_back(states[i][j]);
      }
      //edges.push_back(pii(states[i][j],states[i][j+1]));
    }
  }
  /*bool important[edges.size()];
  rep(i,0,edges.size())important[i]=true;
  rep(i,0,edges.size()){
    rep(j,0,n){
      visited[j]=false;
      nei[j].clear();
    }
    rep(j,0,edges.size()){
      if(j!=i){
	nei[edges[j].first].push_back(edges[j].second);
	nei[edges[j].second].push_back(edges[j].first);
      }
    }
    DFS2(0);
    rep(j,0,n){
      
      important[i]=important[i]&visited[j];
    }
  }*/
  /*rep(i,0,n-1)cout<<important[i];
  cout<<endl;*/
  /*rep(i,0,edges.size()){
    if(important[i]){
      nei[edges[i].first].push_back(edges[i].second);
      nei[edges[i].second].push_back(edges[i].first);
    }
  }
  rep(i,0,n){
    trav(a,nei[i])cout<<a<<" ";
    cout<<endl;
  }cout<<endl;*/
  rep(i,0,n){
    dfs_low[i]=-1;
    dfs_num[i]=-1;
    visited[i]=false;
  }
  counter=0;
  SCC_count=0;
  DFS(0);
  //rep(i,0,n)cout<<SCC[i]<<endl;
  
  /*rep(i,0,n){
    visited[i]=false;
  }*/
  /*SCC_count=0;
  rep(i,0,n){
    if(!visited[i]){
      DFS2(i);
      while(!s.empty()){
	SCC[s.top()]=SCC_count;
	s.pop();
      }
      SCC_count++;
    }
    }*/
  //rep(i,0,n)cout<<SCC[i]<<endl;
  DSU *D=new DSU();
  D->init(SCC_count);
  rep(i,0,k){
    rep(j,0,states[i].size()-1){
      pii new_edge=pii(states[i][j],states[i][j+1]);
      if(!(parent_tree[new_edge.first]!=new_edge.second && parent_tree[new_edge.second]!=new_edge.first)){
	D->merge(SCC[new_edge.first],SCC[new_edge.second]);
      }
      //edges.push_back(pii(states[i][j],states[i][j+1]));
    }
  }
  rep(i,0,n)deg[i]=0;
  trav(a,edges){
    a.first=D->root(SCC[a.first]);
    a.second=D->root(SCC[a.second]);
    if(a.first!=a.second){
      //cout<<a.first<<" "<<a.second<<endl;
      deg[a.first]++;
      deg[a.second]++;
    }
  }
  int leaves=0;
  rep(i,0,SCC_count){
    if(deg[i]==2)leaves++;
  }
  printf("%d\n",(leaves+1)/2);
  return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
mergers.cpp:107:9:
     rep(j,0,states[i].size()-1){
         ~~~~~~~~~~~~~~~~~~~~~~   
mergers.cpp:107:5: note: in expansion of macro 'rep'
     rep(j,0,states[i].size()-1){
     ^~~
mergers.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
mergers.cpp:175:9:
     rep(j,0,states[i].size()-1){
         ~~~~~~~~~~~~~~~~~~~~~~   
mergers.cpp:175:5: note: in expansion of macro 'rep'
     rep(j,0,states[i].size()-1){
     ^~~
mergers.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&k);
   ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&x,&y);
     ~~~~~^~~~~~~~~~~~~~~
mergers.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&state[i]);
     ~~~~~^~~~~~~~~~~~~~~~

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