Submission #140106

#	Time	Username	Problem	Language	Result	Execution time	Memory
140106		KLPP	Mergers (JOI19_mergers)	C++14	0 / 100	147 ms	59612 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];
void DFS(int node){
  dfs_num[node]=counter;
  dfs_low[node]=counter;
  counter++;
  s.push(node);
  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){
	dfs_low[node]=min(dfs_low[node],dfs_low[a]);
      }
    }
  }
  if(dfs_low[node]==dfs_num[node]){
    while(true){
      int u=s.top();
      s.pop();
      SCC[u]=SCC_count;
      dfs_num[u]=-1;
      if(u==node){
	SCC_count++;
	return;
      }
    }
  }
}
int main(){
  scanf("%d %d",&n,&k);
  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));
  }
  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){
      nei[states[i][j]].push_back(states[i][j+1]);
      nei[states[i][j+1]].push_back(states[i][j]);
    }
  }
  rep(i,0,n){
    dfs_low[i]=-1;
    dfs_num[i]=-1;
  }
  counter=0;
  SCC_count=0;
  DFS(0);
  //rep(i,0,n)cout<<SCC[i]<<endl;
  rep(i,0,n)deg[i]=0;
  rep(i,0,n-1){
    if(SCC[edges[i].first]!=SCC[edges[i].second]){
      deg[SCC[edges[i].first]]++;
      deg[SCC[edges[i].second]]++;
    }
  }
  int leaves=0;
  rep(i,0,SCC_count){
    if(deg[i]==1)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:67:9:
     rep(j,0,states[i].size()-1){
         ~~~~~~~~~~~~~~~~~~~~~~   
mergers.cpp:67:5: note: in expansion of macro 'rep'
     rep(j,0,states[i].size()-1){
     ^~~
mergers.cpp:51: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:55: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:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&state[i]);
     ~~~~~^~~~~~~~~~~~~~~~

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