oj.uz

Submission #140109

# Submission time Handle Problem Language Result Execution time Memory
140109 2019-08-02T05:22:52 Z KLPP Mergers (JOI19_mergers) C++14
0 / 100
 148 ms 58112 KB 
#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];
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;
      }
    }
  }
}
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;
    visited[i]=false;
  }
  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

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:70:9:
     rep(j,0,states[i].size()-1){
         ~~~~~~~~~~~~~~~~~~~~~~   
mergers.cpp:70:5: note: in expansion of macro 'rep'
     rep(j,0,states[i].size()-1){
     ^~~
mergers.cpp:54: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:58: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:65: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.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 46 ms 47368 KB Output is correct
8 Correct 45 ms 47352 KB Output is correct
9 Incorrect 46 ms 47300 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 46 ms 47368 KB Output is correct
8 Correct 45 ms 47352 KB Output is correct
9 Incorrect 46 ms 47300 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 46 ms 47368 KB Output is correct
8 Correct 45 ms 47352 KB Output is correct
9 Incorrect 46 ms 47300 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 55892 KB Output is correct
2 Correct 148 ms 58112 KB Output is correct
3 Incorrect 51 ms 47712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 46 ms 47368 KB Output is correct
8 Correct 45 ms 47352 KB Output is correct
9 Incorrect 46 ms 47300 KB Output isn't correct
10 Halted 0 ms 0 KB -