oj.uz

Submission #38201

# Submission time Handle Problem Language Result Execution time Memory
38201 2018-01-03T03:58:19 Z funcsr Synchronization (JOI13_synchronization) C++14
0 / 100
 199 ms 15192 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[100000];
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7876 KB Output is correct
2 Correct 0 ms 7876 KB Output is correct
3 Correct 3 ms 7876 KB Output is correct
4 Correct 0 ms 7876 KB Output is correct
5 Correct 0 ms 7876 KB Output is correct
6 Correct 0 ms 8008 KB Output is correct
7 Correct 16 ms 8536 KB Output is correct
8 Correct 19 ms 8536 KB Output is correct
9 Correct 13 ms 8536 KB Output is correct
10 Runtime error 199 ms 14344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 156 ms 15192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 7876 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 3 ms 7876 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 7876 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -