oj.uz

Submission #849833

# Submission time Handle Problem Language Result Execution time Memory
849833 2023-09-15T12:25:52 Z nguyentunglam Synchronization (JOI13_synchronization) C++17
100 / 100
 251 ms 39300 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()

using namespace std;

const int N = 1e5 + 10;

int st[N], ed[N], a[N], b[N], preans[N], ans[N], rev_st[N];

bool alive[N], active[N];

int timer, n, m, q;

vector<int> adj[N];

priority_queue<int> T[N << 2];

vector<pair<int, int> > edge;

void dfs(int u) {
   st[u] = ++timer;
   rev_st[timer] = u;
   for(int &v : adj[u]) if (!st[v]) dfs(v);
   ed[u] = timer;
}

void up(int s, int l, int r, int from, int to, int val) {
   if (l > to || r < from) return;
   if (from <= l && r <= to) {
      T[s].push(val);
      return;
   }
   int mid = l + r >> 1;
   up(s << 1, l, mid, from, to, val);
   up(s << 1 | 1, mid + 1, r, from, to, val);
}

int get(int s, int l, int r, int pos) {
   while (!T[s].empty() && !alive[T[s].top()]) T[s].pop();
   int head = T[s].empty() ? 1 : T[s].top();
   if (l == r) return head;
   int mid = l + r >> 1;
   if (pos <= mid) return max(head, get(s << 1, l, mid, pos));
   else return max(head, get(s << 1 | 1, mid + 1, r, pos));
}

int root(int v) {
   return rev_st[get(1, 1, n, st[v])];
}

int main() {
   #define task ""

   cin.tie(0) -> sync_with_stdio(0);

   if (fopen ("task.inp", "r")) {
      freopen ("task.inp", "r", stdin);
      freopen ("task.out", "w", stdout);
   }

   if (fopen (task".inp", "r"))  {
      freopen (task".inp", "r", stdin);
      freopen (task".out", "w", stdout);
   }

   cin >> n >> m >> q;

   for(int i = 1; i < n; i++) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
      edge.emplace_back(u, v);
      preans[i] = 0;
   }

   dfs(1);

   for(auto &[u, v] : edge) {
      if (st[u] > st[v]) swap(u, v);
      alive[st[v]] = 1;
      up(1, 1, n, st[v], ed[v], st[v]);
   }

   for(int i = 1; i <= n; i++) ans[i] = 1;

   while (m--) {
      int i; cin >> i;
      active[i] ^= 1;
      int u, v; tie(u, v) = edge[i - 1];
      if (active[i]) {
         alive[st[v]] = 0;
         int r = root(u);
         ans[r] = ans[v] = ans[r] + ans[v] - preans[i];
      }
      if (!active[i]) {
         alive[st[v]] = 1;
         up(1, 1, n, st[v], ed[v], st[v]);
         int r = root(u);
         preans[i] = ans[v] = ans[r];
      }
//      for(int i = 1; i <= n; i++) cout << ans[root(i)] << " "; cout << endl;
   }

   while (q--) {
      int x; cin >> x;
      cout << ans[root(x)] << endl;
   }

}

Compilation message

synchronization.cpp: In function 'void up(int, int, int, int, int, int)':
synchronization.cpp:37:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |    int mid = l + r >> 1;
      |              ~~^~~
synchronization.cpp: In function 'int get(int, int, int, int)':
synchronization.cpp:46:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |    int mid = l + r >> 1;
      |              ~~^~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:61:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |       freopen ("task.inp", "r", stdin);
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:62:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |       freopen ("task.out", "w", stdout);
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:66:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |       freopen (task".inp", "r", stdin);
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:67:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |       freopen (task".out", "w", stdout);
      |       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16984 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 15 ms 18008 KB Output is correct
8 Correct 15 ms 18008 KB Output is correct
9 Correct 16 ms 18008 KB Output is correct
10 Correct 176 ms 28344 KB Output is correct
11 Correct 169 ms 28356 KB Output is correct
12 Correct 207 ms 38336 KB Output is correct
13 Correct 100 ms 27024 KB Output is correct
14 Correct 112 ms 27436 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 33532 KB Output is correct
2 Correct 97 ms 32960 KB Output is correct
3 Correct 90 ms 34240 KB Output is correct
4 Correct 91 ms 34280 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 3 ms 16992 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 3 ms 16984 KB Output is correct
6 Correct 5 ms 16988 KB Output is correct
7 Correct 17 ms 19036 KB Output is correct
8 Correct 231 ms 39292 KB Output is correct
9 Correct 238 ms 39240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 39300 KB Output is correct
2 Correct 117 ms 35364 KB Output is correct
3 Correct 121 ms 35520 KB Output is correct
4 Correct 118 ms 35524 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 5 ms 16984 KB Output is correct
6 Correct 18 ms 18264 KB Output is correct
7 Correct 220 ms 29128 KB Output is correct
8 Correct 251 ms 39148 KB Output is correct
9 Correct 115 ms 28092 KB Output is correct
10 Correct 145 ms 28612 KB Output is correct
11 Correct 128 ms 34676 KB Output is correct
12 Correct 141 ms 34600 KB Output is correct
13 Correct 123 ms 35832 KB Output is correct