oj.uz

Submission #38256

# Submission time Handle Problem Language Result Execution time Memory
38256 2018-01-03T08:32:21 Z funcsr Synchronization (JOI13_synchronization) C++14
60 / 100
 993 ms 20428 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1000001919
int N, M, Q;
vector<P> G[100000];
int evt[200000];
int start[100000];
vector<P> T[100000];
int QV[100000];

int dfs(int x, int p, int time) {
  // cout<<"x="<<x<<" is counted, time="<<time<<"\n";
  int s = 1;
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, e = pp._2;
    auto it = lower_bound(all(T[e]), P(time, -1));
    if (it == T[e].end()) continue;
    s += dfs(t, x, max(it->_2, time));
  }
  return s;
}

int ans[100000];
vector<int> f() {
  vector<bool> used(N-1, false);
  vector<int> ret(N, 1);
  set<int> zeros;
  zeros.insert(-1);
  rep(i, N-1) zeros.insert(i);
  rep(t, M) {
    int e = evt[t];
    if (used[e]) {
      zeros.insert(e);
      used[e] = false;
    }
    else {
      int dest = *(--zeros.find(e))+1;
      ret[dest] += ret[e+1];
      ret[e+1] = 0;
      zeros.erase(e);
      used[e] = true;
    }
  }
  return ret;
}
void solve_linear() {
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (u != i || v != i+1) abort();
  }
  rep(i, M) cin >> evt[i], evt[i]--;
  vector<int> A = f();
  int d = 1;
  rep(i, N) {
    d += A[i]-1;
    ans[i] += d;
  }

  // reverse
  rep(i, M) evt[i] = N-2-evt[i];
  vector<int> B = f();
  reverse(all(B));
  d = 1;
  for (int i=N-1; i>=0; i--) {
    d += B[i]-1;
    ans[i] += d;
  }
  rep(i, N) ans[i]--;

  rep(i, Q) {
    int x;
    cin >> x;
    x--;
    cout << ans[x] << "\n";
  }
}

int main() {
  cin >> N >> M >> Q;
  if (Q == 1) {
    rep(i, N-1) {
      int u, v;
      cin >> u >> v;
      u--, v--;
      G[u].pb(P(v, i));
      G[v].pb(P(u, i));
    }
    rep(i, N-1) start[i] = 0;
    rep(i, M) {
      cin >> evt[i];
      evt[i]--;
      start[evt[i]] ^= 1;
    }
    rep(i, Q) cin >> QV[i], QV[i]--;
    rep(i, N-1) {
      if (start[i]) start[i] = -1;
      else start[i] = INF;
    }
    reverse(evt, evt+M);
    rep(t, M) {
      int e = evt[t];
      if (start[e] == INF) {
        // open
        start[e] = t;
      }
      else {
        // close
        T[e].pb(P(t, start[e]));
        //cout<<"T["<<e<<"]: ["<<start[e]<<","<<t<<"]\n";
        start[e] = INF;
      }
    }
    cout << dfs(QV[0], -1, 0) << "\n";
  }
  else {
    solve_linear();
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8660 KB Output is correct
2 Correct 0 ms 8660 KB Output is correct
3 Correct 0 ms 8660 KB Output is correct
4 Correct 0 ms 8660 KB Output is correct
5 Correct 3 ms 8660 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 19 ms 9320 KB Output is correct
8 Correct 16 ms 9320 KB Output is correct
9 Correct 19 ms 9320 KB Output is correct
10 Correct 196 ms 15128 KB Output is correct
11 Correct 196 ms 15260 KB Output is correct
12 Correct 166 ms 14600 KB Output is correct
13 Correct 186 ms 15664 KB Output is correct
14 Correct 196 ms 15524 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 18976 KB Output is correct
2 Correct 169 ms 17496 KB Output is correct
3 Correct 143 ms 20428 KB Output is correct
4 Correct 126 ms 19608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8660 KB Output is correct
2 Correct 0 ms 8660 KB Output is correct
3 Correct 0 ms 8660 KB Output is correct
4 Correct 0 ms 8660 KB Output is correct
5 Correct 0 ms 8660 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 59 ms 9188 KB Output is correct
8 Correct 776 ms 14200 KB Output is correct
9 Correct 993 ms 14200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 14200 KB Output is correct
2 Correct 449 ms 14064 KB Output is correct
3 Correct 416 ms 14200 KB Output is correct
4 Correct 463 ms 14200 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 8660 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -