Submission #1042523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042523		sleepntsheep	Inside information (BOI21_servers)	C11	52.50 / 100	3600 ms	171344 KiB

servers

#include <stdio.h>
#include <stdlib.h>

int max(int i, int j) { return i > j ? i : j; }
/*
 * For "Q" queries, use LCA + prefix sum on tree ~ 3O(lgn) [for finding lca and almost-lca]
 *
 * Every B queries of any type, do naive dp on tree (reverse edge order)
 * to find answer for "C" queries  ~ O(n)
 *
 * On "C" queries, use cached answer from above and count all edges that appeared after that (by "Q")
 * ~ O(B lgn)
 *
 *
 * Time complexity = O(N^2 / B) + O(N lgn) + O(N B lgn)
 *
 * Let B = sqrt(N / lgN)
 *
 * Should be able to optimize to O(N^1.5) using https://codeforces.com/blog/entry/71567?mobile=true&locale=en 
 */

#define N 120001
#define B 100
#define M 30000000

int n, q, L[M], R[M], A[M], alc, root[N], temp;
int p2(int l, int r, int x) {
  int p = ++alc;
  A[p] = A[L[p]=l] + A[R[p]=r] + x;
  return p;
}
int pbuild(int l, int r) {
  return l == r ? ++alc : p2(pbuild(l, (l+r)/2), pbuild((l+r)/2+1, r), 0);
}
int pupd(int v, int l, int r, int p) {
  if (l == r) {
    return p2(0, 0, 1);
  }
  if (p <= (l+r)/2) return p2(pupd(L[v], l, (l+r)/2, p), R[v], 0);
  return p2(L[v], pupd(R[v], (l+r)/2+1, r, p), 0);
}
int pqry(int v, int l, int r, int k) {
  if (l == r) return l;
  if (A[L[v]] < k) return pqry(R[v], (l+r)/2+1, r, k - A[L[v]]);
  return pqry(L[v], l, (l+r)/2, k);
}
int ppt(int v, int l, int r, int p) {
  if (l == r) return A[v];
  return p <= (l+r)/2 ? ppt(L[v], l, (l+r)/2, p) : ppt(R[v], (l+r)/2+1, r, p);
}

int main() {
  scanf("%d%d", &n, &q);

  root[0] = pbuild(1, n);
  for (int i = 1; i <= n; ++i)
    root[i] = pupd(root[0], 1, n, i);

  q = n + q - 1;
  for (int j = 0, i = 0; i < q; ++i) {
    char type[2];
    int a, b;
    scanf(" %s%d", type, &a);
    if ('S' == type[0]) {
      scanf("%d", &b);
      if (A[root[a]] > A[root[b]])
        temp = a, a = b, b = temp;
      int tot = A[root[a]], at = 0;
      while (at < tot) {
        int p = pqry(root[a], 1, n, ++at);
        root[b] = pupd(root[b], 1, n, p);
      }
      root[a] = root[b];
    } else if ('Q' == type[0]) {
      scanf("%d", &b);
      puts(ppt(root[a], 1, n, b) ? "yes" : "no");
    } else {
      int z=0;for(int i=1;i<=n;++i)z+=ppt(root[i],1,n,a);
      printf("%d\n", z);
    }
  }
}

Compilation message (stderr)

servers.c: In function 'main':
servers.c:61:12: warning: unused variable 'j' [-Wunused-variable]
   61 |   for (int j = 0, i = 0; i < q; ++i) {
      |            ^
servers.c:54:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d%d", &n, &q);
      |   ^~~~~~~~~~~~~~~~~~~~~
servers.c:64:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf(" %s%d", type, &a);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~
servers.c:66:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~
servers.c:76:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5