Submission #1187921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187921		_ncng.nyr	Synchronization (JOI13_synchronization)	C++20	40 / 100	8092 ms	15960 KiB

synchronization

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, k, timer;
int in[N], out[N], rev[N], state[N], ans[N], par[N], pre[N];
pair<int, int> e[N];
vector<int> ad[N];

void dfs (int u, int p) {
  in[u] = ++timer;
  rev[timer] = u;
  for (auto v : ad[u]) if (v != p) {
    par[v] = u;
    dfs(v, u);
  }
  out[u] = timer;
}

int root (int v) {
  while (par[v] != v) v = par[v];
  return v;
}

int32_t main() {
  cin.tie(0) -> sync_with_stdio(0);

  #define task "Synchronization"

  if (fopen ("task.inp", "r")) {
    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);
  }

  if (fopen (task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> m >> k;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
    e[i] = {u, v};
  }
  dfs(1, 0);

  for (int i = 1; i < n; ++i) {
    auto [u, v] = e[i];
    if (in[u] > in[v]) swap(u, v);
    e[i] = {u, v};
  }

  for (int i = 1; i <= n; ++i) ans[i] = 1, par[i] = i;

  for (int i = 1; i <= m; ++i) {
    int id; cin >> id;
    state[id] ^= 1;
    auto [u, v] = e[id];
    if (state[id]) {
      int head = root(u);
      ans[head] = ans[head] + ans[v] - pre[id];
      par[v] = u;
    }
    else {
      int head = root(u);
      pre[id] = ans[v] = ans[head];
      par[v] = v;
    }
  }

  while (k--) {
    int u; cin >> u;
    cout << ans[root(u)] << '\n';
  }
}

Compilation message (stderr)

synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:33:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen ("task.inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:34:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen ("task.out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:38:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:39:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40