提出 #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 |
結果 |
|
|
セット名 |
テストケース |
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 |