oj.uz

Submission #240148

# Submission time Handle Problem Language Result Execution time Memory
240148 2020-06-18T08:04:22 Z quocnguyen1012 Synchronization (JOI13_synchronization) C++14
100 / 100
 374 ms 24440 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 = 1; 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 7 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 7 ms 2816 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 17 ms 4352 KB Output is correct
8 Correct 17 ms 4352 KB Output is correct
9 Correct 20 ms 4480 KB Output is correct
10 Correct 220 ms 18936 KB Output is correct
11 Correct 207 ms 18936 KB Output is correct
12 Correct 260 ms 23416 KB Output is correct
13 Correct 85 ms 18800 KB Output is correct
14 Correct 162 ms 18168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 20728 KB Output is correct
2 Correct 98 ms 20600 KB Output is correct
3 Correct 124 ms 22572 KB Output is correct
4 Correct 125 ms 22700 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 7 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 27 ms 4864 KB Output is correct
8 Correct 320 ms 24312 KB Output is correct
9 Correct 374 ms 24312 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 24184 KB Output is correct
2 Correct 219 ms 23672 KB Output is correct
3 Correct 198 ms 23804 KB Output is correct
4 Correct 190 ms 23800 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 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 25 ms 4480 KB Output is correct
7 Correct 286 ms 19580 KB Output is correct
8 Correct 352 ms 24440 KB Output is correct
9 Correct 128 ms 19952 KB Output is correct
10 Correct 179 ms 19192 KB Output is correct
11 Correct 137 ms 22008 KB Output is correct
12 Correct 138 ms 22008 KB Output is correct
13 Correct 201 ms 23800 KB Output is correct