oj.uz

Submission #30577

# Submission time Handle Problem Language Result Execution time Memory
30577 2017-07-25T04:38:21 Z azneye Synchronization (JOI13_synchronization) C++14
100 / 100
 356 ms 18236 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9072 KB Output is correct
2 Correct 0 ms 9072 KB Output is correct
3 Correct 0 ms 9072 KB Output is correct
4 Correct 0 ms 9072 KB Output is correct
5 Correct 0 ms 9072 KB Output is correct
6 Correct 0 ms 9072 KB Output is correct
7 Correct 19 ms 9336 KB Output is correct
8 Correct 23 ms 9336 KB Output is correct
9 Correct 16 ms 9336 KB Output is correct
10 Correct 286 ms 12240 KB Output is correct
11 Correct 189 ms 12240 KB Output is correct
12 Correct 226 ms 18232 KB Output is correct
13 Correct 169 ms 12624 KB Output is correct
14 Correct 213 ms 12240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 15368 KB Output is correct
2 Correct 119 ms 15396 KB Output is correct
3 Correct 93 ms 18236 KB Output is correct
4 Correct 106 ms 18232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9072 KB Output is correct
2 Correct 3 ms 9072 KB Output is correct
3 Correct 0 ms 9072 KB Output is correct
4 Correct 3 ms 9072 KB Output is correct
5 Correct 3 ms 9072 KB Output is correct
6 Correct 0 ms 9072 KB Output is correct
7 Correct 13 ms 9832 KB Output is correct
8 Correct 276 ms 18236 KB Output is correct
9 Correct 263 ms 18236 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 18236 KB Output is correct
2 Correct 116 ms 18188 KB Output is correct
3 Correct 139 ms 18232 KB Output is correct
4 Correct 153 ms 18232 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9072 KB Output is correct
2 Correct 0 ms 9072 KB Output is correct
3 Correct 0 ms 9072 KB Output is correct
4 Correct 3 ms 9072 KB Output is correct
5 Correct 3 ms 9072 KB Output is correct
6 Correct 26 ms 9336 KB Output is correct
7 Correct 356 ms 12240 KB Output is correct
8 Correct 263 ms 18232 KB Output is correct
9 Correct 243 ms 12624 KB Output is correct
10 Correct 263 ms 12240 KB Output is correct
11 Correct 123 ms 15372 KB Output is correct
12 Correct 139 ms 15372 KB Output is correct
13 Correct 139 ms 18228 KB Output is correct