oj.uz

Submission #240149

# Submission time Handle Problem Language Result Execution time Memory
240149 2020-06-18T08:09:26 Z quocnguyen1012 Synchronization (JOI13_synchronization) C++14
100 / 100
 362 ms 21752 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 6 ms 2688 KB Output is correct
5 Correct 6 ms 2736 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 17 ms 4224 KB Output is correct
8 Correct 18 ms 4224 KB Output is correct
9 Correct 17 ms 4224 KB Output is correct
10 Correct 238 ms 16864 KB Output is correct
11 Correct 206 ms 16760 KB Output is correct
12 Correct 264 ms 21240 KB Output is correct
13 Correct 89 ms 17000 KB Output is correct
14 Correct 145 ms 16376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 18936 KB Output is correct
2 Correct 111 ms 18712 KB Output is correct
3 Correct 126 ms 21020 KB Output is correct
4 Correct 131 ms 20984 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 2816 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 24 ms 4736 KB Output is correct
8 Correct 314 ms 21624 KB Output is correct
9 Correct 318 ms 21496 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 21496 KB Output is correct
2 Correct 187 ms 21496 KB Output is correct
3 Correct 197 ms 21752 KB Output is correct
4 Correct 186 ms 21624 KB Output is correct

Subtask #5
40.0 / 40.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 2816 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 22 ms 4320 KB Output is correct
7 Correct 309 ms 16992 KB Output is correct
8 Correct 362 ms 21496 KB Output is correct
9 Correct 108 ms 17520 KB Output is correct
10 Correct 175 ms 17016 KB Output is correct
11 Correct 141 ms 19584 KB Output is correct
12 Correct 134 ms 19448 KB Output is correct
13 Correct 189 ms 21624 KB Output is correct