結果

問題 No.2588 Increasing Record
コンテスト
ユーザー chro_96
提出日時 2023-12-16 17:33:18
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 34
権限があれば一括ダウンロードができます

ソースコード

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