oj.uz

Submission #38203

# Submission time Handle Problem Language Result Execution time Memory
38203 2018-01-03T03:59:41 Z funcsr Synchronization (JOI13_synchronization) C++14
30 / 100
 223 ms 20028 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 main() {
  cin >> N >> M >> Q;
  if (Q > 1) abort();
  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";
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8264 KB Output is correct
2 Correct 0 ms 8264 KB Output is correct
3 Correct 0 ms 8264 KB Output is correct
4 Correct 0 ms 8264 KB Output is correct
5 Correct 3 ms 8264 KB Output is correct
6 Correct 0 ms 8396 KB Output is correct
7 Correct 16 ms 8924 KB Output is correct
8 Correct 13 ms 8924 KB Output is correct
9 Correct 19 ms 8924 KB Output is correct
10 Correct 203 ms 14732 KB Output is correct
11 Correct 223 ms 14864 KB Output is correct
12 Correct 163 ms 14204 KB Output is correct
13 Correct 163 ms 15268 KB Output is correct
14 Correct 189 ms 15128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 18584 KB Output is correct
2 Correct 143 ms 17096 KB Output is correct
3 Correct 163 ms 20028 KB Output is correct
4 Correct 123 ms 19216 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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