oj.uz

Submission #240150

# Submission time Handle Problem Language Result Execution time Memory
240150 2020-06-18T08:13:02 Z quocnguyen1012 Synchronization (JOI13_synchronization) C++14
100 / 100
 348 ms 21608 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int a[maxn], tin[maxn], tout[maxn], last[maxn];
vector<int> adj[maxn];
ii edge[maxn];
int par[maxn][20];
int N, M, Q;
bool active[maxn];
int bit[maxn];

void upd(int i, int v)
{
  for(; i <= N; i += i & -i)
    bit[i] += v;
}

void rupd(int l, int r, int v)
{
  upd(l, v); upd(r + 1, -v);
}

int sum(int i)
{
  int res = 0;
  for(; i; i -= i & -i)
    res += bit[i];
  return res;
}

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

int root(int u)
{
  for(int i = 19; i >= 0; --i){
    if(par[u][i] && sum(tin[par[u][i]]) == sum(tin[u]))
      u = par[u][i];
  }
  return u;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL

  cin >> N >> M >> Q;
  for(int i = 1; i < N; ++i){
    cin >> edge[i].fi >> edge[i].se;
    adj[edge[i].fi].eb(edge[i].se);
    adj[edge[i].se].eb(edge[i].fi);
  }
  prepare(1);
  for(int i = 2; i <= N; ++i){
    rupd(tin[i], tout[i], 1);
  }
  for(int i = 1; i <= M; ++i){
    int id; cin >> id;
    int u = edge[id].fi, v = edge[id].se;
    if(par[u][0] == v) swap(u, v);
    if(active[id]){
      a[v] = last[v] = a[root(u)];
      rupd(tin[v], tout[v], 1);
    }
    else{
      a[root(u)] += a[v] - last[v];
      rupd(tin[v], tout[v], -1);
    }
    active[id] = !active[id];
  }
  while(Q--){
    int u; cin >> u;
    cout << a[root(u)] << '\n';
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 8 ms 2688 KB Output is correct
5 Correct 7 ms 2688 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 17 ms 4096 KB Output is correct
8 Correct 17 ms 4096 KB Output is correct
9 Correct 17 ms 4096 KB Output is correct
10 Correct 219 ms 16768 KB Output is correct
11 Correct 199 ms 16632 KB Output is correct
12 Correct 254 ms 21240 KB Output is correct
13 Correct 89 ms 16880 KB Output is correct
14 Correct 145 ms 16424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 18808 KB Output is correct
2 Correct 99 ms 18552 KB Output is correct
3 Correct 126 ms 20856 KB Output is correct
4 Correct 126 ms 20928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 24 ms 4608 KB Output is correct
8 Correct 325 ms 21368 KB Output is correct
9 Correct 348 ms 21368 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 21408 KB Output is correct
2 Correct 188 ms 21368 KB Output is correct
3 Correct 188 ms 21496 KB Output is correct
4 Correct 203 ms 21608 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 21 ms 4096 KB Output is correct
7 Correct 258 ms 16888 KB Output is correct
8 Correct 305 ms 21496 KB Output is correct
9 Correct 117 ms 17392 KB Output is correct
10 Correct 181 ms 16888 KB Output is correct
11 Correct 131 ms 19320 KB Output is correct
12 Correct 130 ms 19324 KB Output is correct
13 Correct 189 ms 21496 KB Output is correct