Submission #849833

#	Time	Username	Problem	Language	Result	Execution time	Memory
849833		nguyentunglam	Synchronization (JOI13_synchronization)	C++17	100 / 100	251 ms	39300 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40