제출 #801689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
801689		manizare	Mergers (JOI19_mergers)	C++14	100 / 100	1960 ms	210976 KiB

mergers

#include <bits/stdc++.h>  
#define pii pair <int,int>  
#define F first  
#define S second  
#define all(a) a.begin(),a.end()  
#define pb push_back 
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 10 , inf  = 1e9 , mod = 1e9 + 7 , lg = 21 ;  
int dp[maxn][lg+1] , d[maxn] , dis[maxn]  , c[maxn] , mark[maxn]  , sm[maxn]  ;
vector <int> G[maxn] , vec[maxn] ; 
map <pii ,int>mp ;

int up(int v ,int d){
  for(int i =0 ; i < lg ; i++){
    if(d>>i&1)v = dp[v][i] ; 
  }
  return v; 
}
int lca(int v ,int u){
  if(dis[v] < dis[u])swap(v ,u) ;
  v = up(v , dis[v] - dis[u]) ;
  for(int i = lg-1 ; i >= 0 ; i--){
    if(dp[v][i] != dp[u][i]){
      v = dp[v][i] ;
      u = dp[u][i] ; 
    }
  }
  if(v == u)return v; 
  return dp[v][0] ;
} 

void dfs1(int v ,int p = 0){
  dp[v][0] = p ;
  for(int i = 1; i < lg ; i++)dp[v][i] = dp[dp[v][i-1]][i-1] ; 
  for(int i= 0; i <G[v].size() ; i++){
    int u = G[v][i] ; 
    if(u == p)continue ; 
    dis[u] = dis[v] + 1 ;
    dfs1(u,v) ; 
  }
}

void dfs2(int v ,int p = 0){
  for(int i =0 ; i < G[v].size() ; i++){
    int u = G[v][i] ; 
    if(u == p)continue ;
    dfs2(u , v) ;
    sm[v]+=sm[u];
  }
  if(sm[v] == 0){
    mp[{v,p}] = mp[{p,v}] = 1; 
  }
}
void dfs3(int v , int p  , int cr ){
  c[v]= cr ;mark[v] = 1; 
  for(int i =0 ; i < G[v].size() ; i++){
    int u = G[v][i] ;
    if(u ==p  || mp[{v,u}] == 1)continue ;
    dfs3(u , v , cr) ; 
  }
}

signed main(){ 
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
  int n , k ; cin >> n >> k ; 
  for(int i = 1; i < n ; i++){
    int v ,u  ;
    cin >> v >> u ;
    G[v].pb(u) ;G[u].pb(v) ; 
  }
  dfs1(1) ; 
  for(int i =1 ;i <= n; i++){
    int x ; cin >> x; 
    vec[x].pb(i) ; 
  }
  for(int i = 1; i <= k ; i++){
    int v = vec[i][0] ;
    for(int j = 1 ; j < vec[i].size() ; j++){
      v= lca(v , vec[i][j]) ;  
    }
    for(int j =0 ; j < vec[i].size() ; j++){
      sm[vec[i][j]]++;
      sm[v]--;
    }
  }
  dfs2(1) ;
  int cnt = 1 ; 
  for(int i = 1 ;i <= n ; i++){
    if(mark[i] == 0){
      dfs3(i , 0 , cnt); cnt++ ;
    }
  }
  for(int i = 1; i <= n;  i++){
    for(int j =0 ; j < G[i].size() ; j++){
      int u=  G[i][j] ;
      if(c[u]!=c[i]){
        d[c[u]]++;
      }
    }
  }
  int ans =0 ;
  for(int i = 1; i < cnt ; i++){
    if(d[i]==1)ans++; 
  }
  cout << (ans+1)/2 ;
} 
/* 


*/

컴파일 시 표준 에러 (stderr) 메시지

mergers.cpp: In function 'void dfs1(int, int)':
mergers.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i= 0; i <G[v].size() ; i++){
      |                 ~~^~~~~~~~~~~~
mergers.cpp: In function 'void dfs2(int, int)':
mergers.cpp:45:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i =0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~
mergers.cpp: In function 'void dfs3(int, int, int)':
mergers.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i =0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~
mergers.cpp: In function 'int main()':
mergers.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int j = 1 ; j < vec[i].size() ; j++){
      |                     ~~^~~~~~~~~~~~~~~
mergers.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int j =0 ; j < vec[i].size() ; j++){
      |                    ~~^~~~~~~~~~~~~~~
mergers.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int j =0 ; j < G[i].size() ; j++){
      |                    ~~^~~~~~~~~~~~~

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