oj.uz

Submission #1042536

# Submission time Handle Problem Language Result Execution time Memory
1042536 2024-08-03T06:39:16 Z sleepntsheep Inside information (BOI21_servers) C
50 / 100
 532 ms 170064 KB 
#include <stdio.h>
#include <stdlib.h>

int max(int i, int j) { return i > j ? i : j; }
/*
 * Try merge small 2 large, with persistent ds -> O(nlg^2n)
 * How to maintain "frequency" of each data chunk ? ?? 
 *
 */

#define N 120001
#define B 200
#define M 30000000

int n, q, L[M], R[M], A[M], alc, root[N], temp, dp[N], counted[N];
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 l[B], r[B], k, ds[N];
int find(int i) { return ds[i] == i ? i : (ds[i] = find(ds[i])); }
void run() {
  for (int i = 0; i < B; ++i) {
    int y = dp[r[i]];
    ds[find(l[i])] = find(r[i]);
    dp[r[i]] += dp[l[i]];
    dp[l[i]] += y;
  }
}

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),
    dp[i] = 1, ds[i] = i;

  q = n + q - 1;
  for (int i = 1; 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)
        root[b] = pupd(root[b], 1, n, pqry(root[a], 1, n, ++at));
      root[a] = root[b];
      l[k] = a, r[k] = b;
      if (++k == B)
        run(), k = 0;
    } else if ('Q' == type[0]) {
      scanf("%d", &b);
      puts(ppt(root[a], 1, n, b) ? "yes" : "no");
    } else {
      int z = dp[a];
      for (int j = 0; j < k; ++j) {
        int x[2] = { l[j], r[j] };
        for (int u = 0; u < 2; ++u)
          if (counted[x[u]] != i && find(x[u]) != find(a) &&
              ppt(root[x[u]], 1, n, a))
            ++z, counted[x[u]] = i;
      }
      printf("%d\n", z);
    }
  }
}

Compilation message

servers.c: In function 'main':
servers.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", &n, &q);
      |   ^~~~~~~~~~~~~~~~~~~~~
servers.c:62:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf(" %s%d", type, &a);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~
servers.c:64:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~
servers.c:75:7: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |       scanf("%d", &b);
      |       ^~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 27 ms 2252 KB Output is correct
3 Correct 34 ms 2644 KB Output is correct
4 Correct 26 ms 2384 KB Output is correct
5 Correct 24 ms 2168 KB Output is correct
6 Correct 38 ms 2140 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 27 ms 2252 KB Output is correct
3 Correct 34 ms 2644 KB Output is correct
4 Correct 26 ms 2384 KB Output is correct
5 Correct 24 ms 2168 KB Output is correct
6 Correct 38 ms 2140 KB Output is correct
7 Correct 26 ms 796 KB Output is correct
8 Incorrect 212 ms 2388 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 860 KB Output is correct
2 Correct 200 ms 55456 KB Output is correct
3 Correct 204 ms 55380 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 860 KB Output is correct
2 Correct 200 ms 55456 KB Output is correct
3 Correct 204 ms 55380 KB Output is correct
4 Correct 19 ms 860 KB Output is correct
5 Incorrect 319 ms 55992 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 205 ms 65364 KB Output is correct
3 Correct 181 ms 65312 KB Output is correct
4 Correct 113 ms 55700 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 604 KB Output is correct
2 Correct 205 ms 65364 KB Output is correct
3 Correct 181 ms 65312 KB Output is correct
4 Correct 113 ms 55700 KB Output is correct
5 Correct 19 ms 600 KB Output is correct
6 Incorrect 518 ms 65612 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 600 KB Output is correct
2 Correct 253 ms 144980 KB Output is correct
3 Correct 227 ms 67936 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 600 KB Output is correct
2 Correct 253 ms 144980 KB Output is correct
3 Correct 227 ms 67936 KB Output is correct
4 Correct 20 ms 604 KB Output is correct
5 Incorrect 532 ms 145404 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 228 ms 65340 KB Output is correct
3 Correct 186 ms 65328 KB Output is correct
4 Correct 116 ms 55844 KB Output is correct
5 Correct 16 ms 600 KB Output is correct
6 Correct 296 ms 144976 KB Output is correct
7 Correct 242 ms 67992 KB Output is correct
8 Correct 269 ms 68660 KB Output is correct
9 Correct 280 ms 68656 KB Output is correct
10 Correct 305 ms 77544 KB Output is correct
11 Correct 339 ms 79192 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 228 ms 65340 KB Output is correct
3 Correct 186 ms 65328 KB Output is correct
4 Correct 116 ms 55844 KB Output is correct
5 Correct 16 ms 600 KB Output is correct
6 Correct 296 ms 144976 KB Output is correct
7 Correct 242 ms 67992 KB Output is correct
8 Correct 269 ms 68660 KB Output is correct
9 Correct 280 ms 68656 KB Output is correct
10 Correct 305 ms 77544 KB Output is correct
11 Correct 339 ms 79192 KB Output is correct
12 Correct 19 ms 720 KB Output is correct
13 Incorrect 495 ms 65432 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 684 KB Output is correct
2 Correct 26 ms 2392 KB Output is correct
3 Correct 27 ms 2560 KB Output is correct
4 Correct 26 ms 2648 KB Output is correct
5 Correct 24 ms 2288 KB Output is correct
6 Correct 28 ms 2100 KB Output is correct
7 Correct 15 ms 856 KB Output is correct
8 Correct 204 ms 55632 KB Output is correct
9 Correct 211 ms 55484 KB Output is correct
10 Correct 16 ms 600 KB Output is correct
11 Correct 186 ms 65364 KB Output is correct
12 Correct 200 ms 65172 KB Output is correct
13 Correct 113 ms 55632 KB Output is correct
14 Correct 15 ms 600 KB Output is correct
15 Correct 242 ms 144960 KB Output is correct
16 Correct 213 ms 67924 KB Output is correct
17 Correct 225 ms 68688 KB Output is correct
18 Correct 222 ms 68692 KB Output is correct
19 Correct 245 ms 77568 KB Output is correct
20 Correct 271 ms 79240 KB Output is correct
21 Correct 214 ms 59476 KB Output is correct
22 Correct 291 ms 67112 KB Output is correct
23 Correct 230 ms 71248 KB Output is correct
24 Correct 256 ms 71136 KB Output is correct
25 Correct 221 ms 60248 KB Output is correct
26 Correct 389 ms 160084 KB Output is correct
27 Correct 398 ms 170064 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 684 KB Output is correct
2 Correct 26 ms 2392 KB Output is correct
3 Correct 27 ms 2560 KB Output is correct
4 Correct 26 ms 2648 KB Output is correct
5 Correct 24 ms 2288 KB Output is correct
6 Correct 28 ms 2100 KB Output is correct
7 Correct 15 ms 856 KB Output is correct
8 Correct 204 ms 55632 KB Output is correct
9 Correct 211 ms 55484 KB Output is correct
10 Correct 16 ms 600 KB Output is correct
11 Correct 186 ms 65364 KB Output is correct
12 Correct 200 ms 65172 KB Output is correct
13 Correct 113 ms 55632 KB Output is correct
14 Correct 15 ms 600 KB Output is correct
15 Correct 242 ms 144960 KB Output is correct
16 Correct 213 ms 67924 KB Output is correct
17 Correct 225 ms 68688 KB Output is correct
18 Correct 222 ms 68692 KB Output is correct
19 Correct 245 ms 77568 KB Output is correct
20 Correct 271 ms 79240 KB Output is correct
21 Correct 214 ms 59476 KB Output is correct
22 Correct 291 ms 67112 KB Output is correct
23 Correct 230 ms 71248 KB Output is correct
24 Correct 256 ms 71136 KB Output is correct
25 Correct 221 ms 60248 KB Output is correct
26 Correct 389 ms 160084 KB Output is correct
27 Correct 398 ms 170064 KB Output is correct
28 Correct 20 ms 604 KB Output is correct
29 Incorrect 217 ms 2324 KB Extra information in the output file
30 Halted 0 ms 0 KB -