oj.uz

Submission #202003

# Submission time Handle Problem Language Result Execution time Memory
202003 2020-02-13T03:05:12 Z quocnguyen1012 Mergers (JOI19_mergers) C++14
0 / 100
 110 ms 20776 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

vector<int> adj[maxn];
int N, cnt[maxn], sum[maxn], K;
vector<int> grp[maxn];
int depth[maxn], tin[maxn], tout[maxn], par[maxn][20];

class DSU
{
public:
  vector<int> lab;
  void init(int n)
  {
    lab.assign(n + 5, -1);
  }
  int finds(int u)
  {
    if (lab[u] < 0) return u;
    return lab[u] = finds(lab[u]);
  }
  void merges(int u, int v)
  {
    u = finds(u); v = finds(v);
    if (u == v) return;
    if (lab[v] < lab[u]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
  }
}dsu;

void prepare(int u = 1, int p = -1)
{
  static int nTime = 0;
  tin[u] = ++nTime;
  for (int i = 1; (1 << i) <= N; ++i){
    par[u][i] = par[par[u][i - 1]][i - 1];
  }
  for (int v : adj[u]) if (v != p){
    depth[v] = depth[u] + 1;
    par[v][0] = u;
    prepare(v, u);
  }
  tout[u] = nTime;
}

int LCA(int x, int y)
{
  if (depth[y] > depth[x]) swap(x, y);
  for (int k = 19; k >= 0; --k){
    if (depth[par[x][k]] >= depth[y]){
      x = par[x][k];
    }
  }
  if (x == y) return x;
  for (int k = 19; k >= 0; --k){
    if (par[x][k] != par[y][k]){
      x = par[x][k];
      y = par[y][k];
    }
  }
  return par[x][0];
}

void DFS(int u, int p = -1)
{
  for (int v : adj[u]) if (v != p){
    DFS(v, u);
    sum[u] += sum[v];
  }
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> K; dsu.init(N);
  for (int i = 1; i < N; ++i){
    int u, v; cin >> u >> v;
    adj[u].pb(v); adj[v].pb(u);
  }
  for (int i = 1; i <= N; ++i){
    int v; cin >> v;
    grp[v].pb(i);
  }
  depth[1] = 1;
  prepare();
  for (int i = 1; i <= K; ++i){
    sort(grp[i].begin(), grp[i].end(),
      [&](const int & x, const int & y){
        return tin[x] < tin[y];
      }
    );
    for (int j = 0; j < (int)grp[i].size() - 1; ++j){
      sum[grp[i][j]]++; sum[grp[i][j + 1]]++;
      sum[LCA(grp[i][j], grp[i][j + 1])] -= 2;
    }
  }
  DFS(1);
  for (int i = 2; i <= N; ++i){
    if (sum[i] == 1){
      dsu.merges(i, par[i][0]);
    }
  }
  for (int i = 2; i <= N; ++i){
    int l = dsu.finds(i);
    int r = dsu.finds(par[i][0]);
    if (l != r) ++cnt[l], ++cnt[r];
  }
  int res = 0;
  for (int i = 1; i <= N; ++i){
    res += (cnt[i] == 1);
  }
  cout << (res + 1) / 2;
}

Compilation message

mergers.cpp: In function 'int main()':
mergers.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
mergers.cpp:87:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Incorrect 8 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Incorrect 8 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Incorrect 8 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 20776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Incorrect 8 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -