提出 #47507423


ソースコード 拡げる

/*
Author : Hocky Yudhiono
Sab 11 Nov 2023 07:52:07
*/

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<LL, LL> PLL;
typedef pair<LL, LL> pll;
typedef long double ld;
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second
#define int long long

const double EPS = 1e-9;
const int INFMEM = 63;

// Do dir^1 to get reverse direction
const int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
const char dch[4] = {'R', 'L', 'D', 'U'};

// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;

inline void fasterios() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}
const int MOD = 1000000007;
// const int MOD = 998244353;

#undef all
#undef sz

const int MAX = 4e5 + 10;

struct Data {
  LL sum, mn, mx, sz;

  Data() : sum(0), mn(LLONG_MAX), mx(LLONG_MIN), sz(0) {}

  Data(LL val) : sum(val), mn(val), mx(val), sz(1) {}

  Data(LL _sum, LL _mn, LL _mx, LL _sz) : sum(_sum), mn(_mn), mx(_mx), sz(_sz) {}
};

struct Lazy {
  LL a, b;
  Lazy(LL _a = 1, LL _b = 0) : a(_a), b(_b) {}
  bool lazy() {
    return a != 1 || b != 0;
  }
};

Data operator + (const Data &a, const Data &b) {
  return Data(a.sum + b.sum, min(a.mn, b.mn), max(a.mx, b.mx), a.sz + b.sz);
}

Data& operator += (Data &a, const Data &b) {
  return a = a + b;
}

Lazy& operator += (Lazy &a, const Lazy &b) {
  return a = Lazy(a.a * b.a, a.b * b.a + b.b);
}

LL& operator += (LL &a, const Lazy &b) {
  return a = a * b.a + b.b;
}

Data& operator += (Data &a, const Lazy &b) {
  return a.sz ? a = Data(a.sum * b.a + a.sz * b.b, a.mn * b.a + b.b, a.mx * b.a + b.b, a.sz) : a;
}

struct Node {
  LL p, ch[4], val;
  Data path, sub, all;
  Lazy plazy, slazy;
  bool flip, fake;

  Node() : p(0), ch(), path(), sub(), all(), plazy(), slazy(), flip(false), fake(true) {}

  Node(LL _val) : Node() {
    val = _val;
    path = all = Data(val);
    fake = false;
  }
} tr[MAX];
vector<LL> freeList;

void pushFlip(LL u) {
  if (!u)
    return;
  swap(tr[u].ch[0], tr[u].ch[1]);
  tr[u].flip ^= true;
}

void pushPath(LL u, const Lazy &lazy) {
  if (!u || tr[u].fake)
    return;
  tr[u].val += lazy;
  tr[u].path += lazy;
  tr[u].all = tr[u].path + tr[u].sub;
  tr[u].plazy += lazy;
}

void pushSub(LL u, bool o, const Lazy &lazy) {
  if (!u)
    return;
  tr[u].sub += lazy;
  tr[u].slazy += lazy;
  if (!tr[u].fake && o)
    pushPath(u, lazy);
  else
    tr[u].all = tr[u].path + tr[u].sub;
}

void push(LL u) {
  if (!u)
    return;
  if (tr[u].flip) {
    pushFlip(tr[u].ch[0]);
    pushFlip(tr[u].ch[1]);
    tr[u].flip = false;
  }
  if (tr[u].plazy.lazy()) {
    pushPath(tr[u].ch[0], tr[u].plazy);
    pushPath(tr[u].ch[1], tr[u].plazy);
    tr[u].plazy = Lazy();
  }
  if (tr[u].slazy.lazy()) {
    pushSub(tr[u].ch[0], false, tr[u].slazy);
    pushSub(tr[u].ch[1], false, tr[u].slazy);
    pushSub(tr[u].ch[2], true, tr[u].slazy);
    pushSub(tr[u].ch[3], true, tr[u].slazy);
    tr[u].slazy = Lazy();
  }
}

void pull(LL u) {
  if (!tr[u].fake)
    tr[u].path = tr[tr[u].ch[0]].path + tr[tr[u].ch[1]].path + tr[u].val;
  tr[u].sub = tr[tr[u].ch[0]].sub + tr[tr[u].ch[1]].sub + tr[tr[u].ch[2]].all + tr[tr[u].ch[3]].all;
  tr[u].all = tr[u].path + tr[u].sub;
}

void attach(LL u, LL d, LL v) {
  tr[u].ch[d] = v;
  tr[v].p = u;
  pull(u);
}

int dir(int u, int o) {
  int v = tr[u].p;
  return tr[v].ch[o] == u ? o : tr[v].ch[o + 1] == u ? o + 1 : -1;
}

void rotate(int u, int o) {
  int v = tr[u].p, w = tr[v].p, du = dir(u, o), dv = dir(v, o);
  if (dv == -1 && o == 0)
    dv = dir(v, 2);
  attach(v, du, tr[u].ch[du ^ 1]);
  attach(u, du ^ 1, v);
  if (~dv)
    attach(w, dv, u);
  else
    tr[u].p = w;
}

void splay(int u, int o) {
  push(u);
  while (~dir(u, o) && (o == 0 || tr[tr[u].p].fake)) {
    int v = tr[u].p, w = tr[v].p;
    push(w);
    push(v);
    push(u);
    int du = dir(u, o), dv = dir(v, o);
    if (~dv && (o == 0 || tr[w].fake))
      rotate(du == dv ? v : u, o);
    rotate(u, o);
  }
}

void add(int u, int v) {
  if (!v)
    return;
  for (int i = 2; i < 4; i++)
    if (!tr[u].ch[i]) {
      attach(u, i, v);
      return;
    }
  int w = freeList.back();
  freeList.pop_back();
  attach(w, 2, tr[u].ch[2]);
  attach(w, 3, v);
  attach(u, 2, w);
}

void recPush(int u) {
  if (tr[u].fake)
    recPush(tr[u].p);
  push(u);
}

void rem(int u) {
  int v = tr[u].p;
  recPush(v);
  if (tr[v].fake) {
    int w = tr[v].p;
    attach(w, dir(v, 2), tr[v].ch[dir(u, 2) ^ 1]);
    if (tr[w].fake)
      splay(w, 2);
    freeList.push_back(v);
  } else {
    attach(v, dir(u, 2), 0);
  }
  tr[u].p = 0;
}

int par(int u) {
  int v = tr[u].p;
  if (!tr[v].fake)
    return v;
  splay(v, 2);
  return tr[v].p;
}

int access(int u) {
  int v = u;
  splay(u, 0);
  add(u, tr[u].ch[1]);
  attach(u, 1, 0);
  while (tr[u].p) {
    v = par(u);
    splay(v, 0);
    rem(u);
    add(v, tr[v].ch[1]);
    attach(v, 1, u);
    splay(u, 0);
  }
  return v;
}

void reroot(int u) {
  access(u);
  pushFlip(u);
}

void link(int u, int v) {
  reroot(u);
  access(v);
  add(v, u);
}

void cut(int u, int v) {
  reroot(u);
  access(v);
  tr[v].ch[0] = tr[u].p = 0;
  pull(v);
}

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()


struct UF {
  vi e;
  UF(int n) : e(n + 1, -1) {}
  bool sameSet(int a, int b) { return find(a) == find(b); }
  int size(int x) { return -e[find(x)]; }
  int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
  bool join(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (e[a] > e[b]) swap(a, b);
    e[a] += e[b]; e[b] = a;
    return true;
  }
};


int32_t main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);
  UF solver(MAX + 5);
  int n, m;
  cin >> n >> m; n++;
  for (int i = 1; i <= n; i++) tr[i] = Node(0);
  for (int i = n + 1; i < MAX; i++)
    freeList.push_back(i);
  vector <LL> ans;
  rep(qq, 1, m + 1) {
    LL a, b, d; cin >> a >> b >> d;
    if (solver.join(a, b)) {
      ans.pb(qq);
      // New link
      link(a, b);
      reroot(b);
      access(b);
      Data ret = tr[b].path;
      reroot(a);
      access(a);
      Data ret2 = tr[a].path;
      LL curdiff = ret2.sum - ret.sum;
      LL nextDiff = curdiff - d;
      int x = b, y = nextDiff;

      reroot(a);
      access(x);
      Lazy lazy(true, y);
      tr[x].val += lazy;
      for (int i = 2; i < 4; i++)
        pushSub(tr[x].ch[i], true, lazy);

    } else {
      reroot(a);
      access(a);
      Data ret = tr[a].path;
      reroot(b);
      access(b);
      Data ret2 = tr[b].path;
      if (ret.sum - ret2.sum == d) ans.pb(qq);
    }
  }
  trav(cur, ans) cout << cur << " ";
  cout << endl;

  return 0;
}

提出情報

提出日時
問題 F - Good Set Query
ユーザ hocky
言語 C++ 20 (gcc 12.2)
得点 525
コード長 7458 Byte
結果 AC
実行時間 1180 ms
メモリ 83444 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 525 / 525
結果
AC × 3
AC × 39
セット名 テストケース
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, example0.txt, example1.txt, example2.txt, hack_001.txt, hack_002.txt
ケース名 結果 実行時間 メモリ
000.txt AC 101 ms 81580 KiB
001.txt AC 166 ms 83324 KiB
002.txt AC 140 ms 81336 KiB
003.txt AC 126 ms 78780 KiB
004.txt AC 134 ms 80004 KiB
005.txt AC 232 ms 81264 KiB
006.txt AC 243 ms 81248 KiB
007.txt AC 236 ms 81324 KiB
008.txt AC 238 ms 81344 KiB
009.txt AC 277 ms 83420 KiB
010.txt AC 163 ms 80724 KiB
011.txt AC 149 ms 81556 KiB
012.txt AC 146 ms 83396 KiB
013.txt AC 129 ms 83316 KiB
014.txt AC 347 ms 80796 KiB
015.txt AC 350 ms 81568 KiB
016.txt AC 355 ms 83444 KiB
017.txt AC 273 ms 83444 KiB
018.txt AC 602 ms 80800 KiB
019.txt AC 604 ms 81520 KiB
020.txt AC 620 ms 83400 KiB
021.txt AC 441 ms 83328 KiB
022.txt AC 860 ms 80724 KiB
023.txt AC 875 ms 81640 KiB
024.txt AC 865 ms 83332 KiB
025.txt AC 601 ms 83332 KiB
026.txt AC 1173 ms 80876 KiB
027.txt AC 1180 ms 81568 KiB
028.txt AC 1177 ms 83152 KiB
029.txt AC 743 ms 83148 KiB
030.txt AC 877 ms 81320 KiB
031.txt AC 874 ms 81252 KiB
032.txt AC 889 ms 81276 KiB
033.txt AC 494 ms 81320 KiB
example0.txt AC 29 ms 80976 KiB
example1.txt AC 31 ms 78644 KiB
example2.txt AC 29 ms 80720 KiB
hack_001.txt AC 29 ms 80720 KiB
hack_002.txt AC 29 ms 80744 KiB