oj.uz

Submission #137989

# Submission time Handle Problem Language Result Execution time Memory
137989 2019-07-28T17:48:56 Z triplem5ds Mergers (JOI19_mergers) C++14
0 / 100
 221 ms 19724 KB 
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
using ll = long long;
using ii = pair<int, int>;
const int N = 5e5 + 5, mod = 1e9 + 7;
int n, k;
std::vector<int> adj[N];
int in[N], out[N], ord[N], lvl[N], sz[N], timer;
int cnt[N];
int cur[N];
int col[N];
int freq[N];
void dfs0(int u){
  sz[u] = 1;
  in[u] = timer;
  for(auto v : adj[u]){
    lvl[v] = lvl[u] + 1;
    adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
    dfs0(v);
    sz[u] += sz[v];
  }
  ord[timer] = u;
  out[u] = timer++;
}
bool f;
int ans[N];
bool isFaulty[N];
int dfs1(int u, bool keep) {
  int mx = -1, bigChild = -1;
  for(auto v : adj[u])if(sz[v] > mx){
    mx = sz[v], bigChild = v;
  }
  if(bigChild == -1){
    cur[u] = k - 1;
    cnt[col[u]]++;
    cur[u] += (cnt[col[u]] == freq[col[u]]);
    int ret = cur[u] == k;
    // cout << freq[col[u]] << ' ' << cnt[col[u]] << ' ' << cur[u] << ' ' << ret  << '\n';
    if(!keep){
      cur[u] -= (cnt[col[u]] == freq[col[u]]);
      cnt[col[u]]--;
      cur[u] += (cnt[col[u]] == 0);
    }
    // cout << u << ' ' << ret << '\n';
    isFaulty[u] = ret;
    return ans[u] = ret;
  }
  int ret = 0;
  for(auto v : adj[u])if(v != bigChild){
    ret += dfs1(v, 0);
  }
  // cout << u << ' ' << ret << '\n';
  ret += dfs1(bigChild, 1);
  cur[u] = cur[bigChild];
  for(auto v : adj[u])
  if(v != bigChild){
    for(int x = in[v]; x <= out[v]; x++){
      cur[u] -= (cnt[col[ord[x]]] == 0);
      cnt[col[ord[x]]]++;
      cur[u] += (cnt[col[ord[x]]] == freq[col[ord[x]]]);
    }
  }
  cur[u] -= (cnt[col[u]] == 0);
  cnt[col[u]]++;
  cur[u] += (cnt[col[u]] == freq[col[u]]);
  if(!ret && u != 1){
    ret = cur[u] == k;
    isFaulty[u] = ret;
  }
  if(!keep){
    for(int x = in[u]; x <= out[u]; x++){
      cur[u] -= (cnt[col[ord[x]]] == freq[col[ord[x]]]);
      cnt[col[ord[x]]]--;
      cur[u] += (cnt[col[ord[x]]] == 0);
    }
  }
  return ans[u] = ret;
}
int main(){

  cin >> n >> k;

  for(int i = 0, u, v; i < n - 1; i++){
    cin >> u >> v;
    adj[u].pb(v);
    adj[v].pb(u);
  }
  for(int i = 1; i <= n; i++){
    cin >> col[i];
    freq[col[i]]++;
  }
  dfs0(1);
  if(min(n,k) == 1){
    cout << 0 << endl;
    return 0;
  }
  int out = dfs1(1, 0) + 1;
  for(int i = 2; i <= n; i++)
  if(isFaulty[i]){
    int tot = 0;
    for(auto v : adj[i])tot += ans[v];
    if(tot == out - 1){
      out++;
      break;
    }
  }

  cout << out / 2 << '\n';

  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 13 ms 12156 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 14 ms 12152 KB Output is correct
9 Correct 14 ms 12156 KB Output is correct
10 Correct 13 ms 12152 KB Output is correct
11 Correct 14 ms 12196 KB Output is correct
12 Correct 13 ms 12152 KB Output is correct
13 Correct 14 ms 12152 KB Output is correct
14 Correct 13 ms 12096 KB Output is correct
15 Correct 14 ms 12152 KB Output is correct
16 Incorrect 14 ms 12156 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 13 ms 12156 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 14 ms 12152 KB Output is correct
9 Correct 14 ms 12156 KB Output is correct
10 Correct 13 ms 12152 KB Output is correct
11 Correct 14 ms 12196 KB Output is correct
12 Correct 13 ms 12152 KB Output is correct
13 Correct 14 ms 12152 KB Output is correct
14 Correct 13 ms 12096 KB Output is correct
15 Correct 14 ms 12152 KB Output is correct
16 Incorrect 14 ms 12156 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 13 ms 12156 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 14 ms 12152 KB Output is correct
9 Correct 14 ms 12156 KB Output is correct
10 Correct 13 ms 12152 KB Output is correct
11 Correct 14 ms 12196 KB Output is correct
12 Correct 13 ms 12152 KB Output is correct
13 Correct 14 ms 12152 KB Output is correct
14 Correct 13 ms 12096 KB Output is correct
15 Correct 14 ms 12152 KB Output is correct
16 Incorrect 14 ms 12156 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 18988 KB Output is correct
2 Incorrect 221 ms 19724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 13 ms 12152 KB Output is correct
4 Correct 13 ms 12152 KB Output is correct
5 Correct 13 ms 12152 KB Output is correct
6 Correct 13 ms 12156 KB Output is correct
7 Correct 13 ms 12152 KB Output is correct
8 Correct 14 ms 12152 KB Output is correct
9 Correct 14 ms 12156 KB Output is correct
10 Correct 13 ms 12152 KB Output is correct
11 Correct 14 ms 12196 KB Output is correct
12 Correct 13 ms 12152 KB Output is correct
13 Correct 14 ms 12152 KB Output is correct
14 Correct 13 ms 12096 KB Output is correct
15 Correct 14 ms 12152 KB Output is correct
16 Incorrect 14 ms 12156 KB Output isn't correct
17 Halted 0 ms 0 KB -