Submission #30577

#	Time	Username	Problem	Language	Result	Execution time	Memory
30577		azneye	Synchronization (JOI13_synchronization)	C++14	100 / 100	356 ms	18236 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

namespace {

#define VERA(i, a, b)for(auto i=(ll)(a);i<(ll)(b);++i)
#define ANDY(i, a, b)for(auto i=(ll)(a);i>(ll)(b);--i)

typedef long long ll;
typedef long double dd;

template <class T> using V = vector<T>;

// Maintain array A[0, n-1] initially all -1
// Given k, x: Set A[k] = x
// Given b, x: Find max p such that 0 <= p <= b and A[p] >= x
struct SegTree {
  static const int PW = 1 << 17;
  int max_val[2 * PW];

  void Init() {
    memset(max_val, -1, sizeof(max_val));
  }

  void Set(int pos, int val) {
    max_val[pos += PW] = val;
    for (int i = pos >> 1; i > 0; i >>= 1)
      max_val[i] = max(max_val[2 * i], max_val[2 * i + 1]);
  }

  int Query(int b, int x, int at = 1, int l = 0, int r = PW - 1) {
    if (max_val[at] < x)
      return -1;
    if (l == r)
      return l;
    const int m = (l + r) >> 1;
    if (b > m) {
      const int u = Query(b, x, 2 * at + 1, m + 1, r);
      if (u != -1)
        return u;
    }
    return Query(b, x, 2 * at, l, m);
  }
};

const int MAX = 100100;
V<int> adj[MAX];
int lef_cnt, rig_cnt;
int depth[MAX], lid[MAX], rid[MAX], lrev[MAX];
int val[MAX], val_last_cut[MAX], e_x[MAX], e_y[MAX], e_on[MAX];
SegTree tree;

void dfs(int at, int par, int cur_dep = 0) {
  depth[at] = cur_dep;
  lrev[lef_cnt] = at;
  lid[at] = lef_cnt++;
  for (int to: adj[at]) {
    if (to == par) continue;
    dfs(to, at, cur_dep + 1);
  }
  rid[at] = rig_cnt++;
}

void Solve(ll test_num) {
  (void) test_num;
  int n, m, q;
  scanf("%d %d %d", &n, &m, &q);
  VERA(i, 0, n - 1) {
    scanf("%d %d", e_x + i, e_y + i);
    e_x[i]--;
    e_y[i]--;
    adj[e_x[i]].push_back(e_y[i]);
    adj[e_y[i]].push_back(e_x[i]);
  }
  lef_cnt = rig_cnt = 0;
  dfs(0, -1);
  tree.Init();
  auto root = [&](int vertex) {
    return lrev[tree.Query(lid[vertex], rid[vertex])];
  };
  auto add_vert = [&](int vertex) {
    tree.Set(lid[vertex], rid[vertex]);
  };
  auto erase_vert = [&](int vertex) {
    tree.Set(lid[vertex], -1);
  };
//  memset(pool, 0, sizeof(pool));
  VERA(i, 0, n) {
    add_vert(i);
  }
  fill(val, val + n, 1);
//  VERA(i, 0, n) {
//    ++val[root(i)];
//  }
  memset(val_last_cut, 0, sizeof(val_last_cut));
  VERA(i, 0, m) {
    int e;
    scanf("%d", &e);
    --e;
    int x = e_x[e], y = e_y[e];
    if (depth[x] < depth[y])
      swap(x, y);
    // y is parent of x
    if (!e_on[e]) {
      // merge
      //inc
      val[root(y)] += val[x] - val_last_cut[x];
      erase_vert(x);
    } else {
      // cut
      //dec
      val[x] = val_last_cut[x] = val[root(y)];
      add_vert(x);
    }
    e_on[e] = 1 - e_on[e];
  }
  VERA(i, 0, q) {
    int x;
    scanf("%d", &x);
    x--;
    printf("%d\n", val[root(x)]);
  }
}

void Init() {
}

}

int main() {
#ifdef AZN
  const auto start_time = chrono::system_clock::now();
  freopen("../input.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  srand(1223);
  Init();
  ll tests = 1;
//  cin >> tests;
  VERA(test, 1, tests + 1) {
    Solve(test);
  }
#ifdef AZN
  cerr << "Took: " << ((chrono::system_clock::now() - start_time).count() / 1e9) << " s" << endl;
#endif
  return 0;
}

Compilation message (stderr)

synchronization.cpp: In function 'void {anonymous}::Solve({anonymous}::ll)':
synchronization.cpp:68:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &n, &m, &q);
                                ^
synchronization.cpp:70:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", e_x + i, e_y + i);
                                     ^
synchronization.cpp:99:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &e);
                    ^
synchronization.cpp:120:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &x);
                    ^

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