結果

問題 No.2588 Increasing Record
ユーザー chro_96chro_96
提出日時 2023-12-16 17:33:18
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 3,914 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 32,428 KB
実行使用メモリ 28,468 KB
最終ジャッジ日時 2024-09-27 07:47:08
合計ジャッジ時間 6,680 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
28,356 KB
testcase_01 AC 7 ms
28,432 KB
testcase_02 AC 7 ms
28,416 KB
testcase_03 AC 8 ms
28,456 KB
testcase_04 AC 8 ms
28,416 KB
testcase_05 AC 8 ms
28,456 KB
testcase_06 AC 7 ms
28,328 KB
testcase_07 AC 8 ms
28,388 KB
testcase_08 WA -
testcase_09 AC 8 ms
28,388 KB
testcase_10 WA -
testcase_11 AC 8 ms
28,448 KB
testcase_12 AC 91 ms
28,268 KB
testcase_13 AC 93 ms
28,320 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 68 ms
28,448 KB
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef struct btree {
  int rnd;
  int v;
  int n;
  struct btree *l;
  struct btree *r;
} btree;

typedef struct tree {
  struct tree *p;
  int n;
  long long adj;
  btree *s;
} tree;

typedef struct list {
  int v;
  struct list *n;
} list;

tree *get_root (tree *t) {
  if (t == NULL || t->p == NULL) {
    return t;
  }
  
  t->p = get_root(t->p);
  return t->p;
}

int is_member (btree *t, int v) {
  if (t == NULL) {
    return 0;
  }
  
  if (t->v == v) {
    return 1;
  }
  
  if (v < t->v) {
    return is_member(t->l, v);
  }
  
  return is_member(t->r, v);
}

btree *insert_btree (btree *t, btree *n) {
  if (n == NULL) {
    return t;
  }
  
  if (t == NULL) {
    n->n = 1;
    n->l = NULL;
    n->r = NULL;
    return n;
  }
  
  if (n->v < t->v) {
    t->l = insert_btree(t->l, n);
    if (t->rnd > t->l->rnd) {
      btree *tmp = t->l;
      t->l = tmp->r;
      tmp->r = t;
      t->n = 1;
      if (t->l != NULL) {
        t->n += t->l->n;
      }
      if (t->r != NULL) {
        t->n += t->r->n;
      }
      t = tmp;
    }
  } else {
    t->r = insert_btree(t->r, n);
    if (t->rnd > t->r->rnd) {
      btree *tmp = t->r;
      t->r = tmp->l;
      tmp->l = t;
      t->n = 1;
      if (t->l != NULL) {
        t->n += t->l->n;
      }
      if (t->r != NULL) {
        t->n += t->r->n;
      }
      t = tmp;
    }
  }
  
  t->n = 1;
  if (t->l != NULL) {
    t->n += t->l->n;
  }
  if (t->r != NULL) {
    t->n += t->r->n;
  }
  
  return t;
}

int main () {
  int n = 0;
  int m = 0;
  int u = 0;
  int v = 0;
  
  int res = 0;
  
  long long ans = 0LL;
  long long mod_num = 998244353LL;
  
  tree t[200000] = {};
  long long cnt[200000] = {};
  
  list pool[400000] = {};
  int used = 0;
  
  list *e1[200000] = {};  
  list *e2[200000] = {};
  
  btree bpool[200000] = {};
  int bused = 0;
  
  btree *q[400000] = {};
  
  srand(1);
  
  res = scanf("%d", &n);
  res = scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    res = scanf("%d", &u);
    res = scanf("%d", &v);
    u--;
    v--;
    pool[used].v = v;
    pool[used].n = e1[u];
    e1[u] = pool+used;
    used++;
    pool[used].v = u;
    pool[used].n = e2[v];
    e2[v] = pool+used;
    used++;
  }
  
  for (int i = 0; i < n; i++) {
    list *l = e1[i];
    tree *rt = NULL;
    cnt[i] += 1LL;
    t[i].p = NULL;
    t[i].n = 0;
    t[i].adj = 0LL;
    t[i].s = NULL;
    ans += cnt[i];
    while (l != NULL) {
      bpool[bused].rnd = rand();
      bpool[bused].v = l->v;
      bpool[bused].n = 1;
      bpool[bused].l = NULL;
      bpool[bused].r = NULL;
      t[i].s = insert_btree(t[i].s, bpool+bused);
      bused++;
      t[i].n += 1;
      l = l->n;
    }
    l = e2[i];
    while (l != NULL) {
      tree *rt1 = get_root(t+i);
      tree *rt2 = get_root(t+l->v);
      if (rt1 != rt2) {
        int q_hd = 0;
        int q_tl = 0;
        cnt[i] += rt2->adj;
        ans += rt2->adj;
        if (rt1->n > rt2->n) {
          tree *swap = rt1;
          rt1 = rt2;
          rt2 = swap;
        }
        q[q_tl] = rt1->s;
        q_tl++;
        while (q_hd < q_tl) {
          btree *tmp = q[q_hd];
          q_hd++;
          if (tmp != NULL && tmp->v > i) {
            q[q_tl] = tmp->l;
            q_tl++;
            q[q_tl] = tmp->r;
            q_tl++;
            if (is_member(rt2->s, tmp->v) > 0) {
              cnt[tmp->v] += rt1->adj;
              cnt[tmp->v] %= mod_num;
            } else {
              cnt[tmp->v] += rt1->adj+mod_num-rt2->adj;
              cnt[tmp->v] %= mod_num;
              tmp->n = 1;
              tmp->l = NULL;
              tmp->r = NULL;
              rt2->s = insert_btree(rt2->s, tmp);
              rt2->n++;
            }
          }
        }
        rt1->p = rt2;
      }
      l = l->n;
    }
    rt = get_root(t+i);
    rt->adj += cnt[i];
    rt->adj %= mod_num;
  }
  
  printf("%lld\n", ans%mod_num);
  return 0;
}
0