summaryrefslogtreecommitdiff
path: root/kattis-open-almostunionfind
diff options
context:
space:
mode:
Diffstat (limited to 'kattis-open-almostunionfind')
-rw-r--r--kattis-open-almostunionfind/Cargo.lock7
-rw-r--r--kattis-open-almostunionfind/Cargo.toml8
-rwxr-xr-xkattis-open-almostunionfind/bad.py53
-rwxr-xr-xkattis-open-almostunionfind/geninput.py15
-rw-r--r--kattis-open-almostunionfind/in2.txt8
-rw-r--r--kattis-open-almostunionfind/in3.txt241
-rw-r--r--kattis-open-almostunionfind/input.txt41
-rw-r--r--kattis-open-almostunionfind/pyout.txt281
-rw-r--r--kattis-open-almostunionfind/rustout.txt281
-rw-r--r--kattis-open-almostunionfind/src/main.rs153
10 files changed, 1088 insertions, 0 deletions
diff --git a/kattis-open-almostunionfind/Cargo.lock b/kattis-open-almostunionfind/Cargo.lock
new file mode 100644
index 0000000..f79cc3f
--- /dev/null
+++ b/kattis-open-almostunionfind/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "kattis-open-almostunionfind"
+version = "0.1.0"
diff --git a/kattis-open-almostunionfind/Cargo.toml b/kattis-open-almostunionfind/Cargo.toml
new file mode 100644
index 0000000..e40a8b1
--- /dev/null
+++ b/kattis-open-almostunionfind/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "kattis-open-almostunionfind"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/kattis-open-almostunionfind/bad.py b/kattis-open-almostunionfind/bad.py
new file mode 100755
index 0000000..1d4cbec
--- /dev/null
+++ b/kattis-open-almostunionfind/bad.py
@@ -0,0 +1,53 @@
+#!/usr/bin/python
+
+while True:
+ try:
+ line = input()
+ except EOFError:
+ break
+ n, m = map(int, line.split())
+
+ u = [[i + 1] for i in range(n)]
+
+ for _ in range(m):
+ line = input().split()
+ p = int(line[1])
+ if line[0] != '3':
+ q = int(line[2])
+
+ if line[0] == '1': # union
+ a, b = False, False
+ for s in u:
+ if p in s:
+ a = s
+ if q in s:
+ b = s
+ if a == False or b == False:
+ raise ValueError(f"could not find {p} or {q} in {u}")
+ if a != b:
+ for i in b:
+ a.append(i)
+ b.clear()
+ u.remove(b)
+ elif line[0] == '2': # move
+ a, b = False, False
+ for s in u:
+ if p in s:
+ a = s
+ if q in s:
+ b = s
+ if a == False or b == False:
+ raise ValueError(f"could not find {p} or {q} in {u}")
+ if a != b:
+ a.remove(p)
+ b.append(p)
+ if not a:
+ u.remove(a)
+ elif line[0] == '3':
+ for s in u:
+ if p in s:
+ print(len(s), sum(s))
+ break
+ else:
+ raise ValueError(f"could not find {p} in {u}")
+ # print(u)
diff --git a/kattis-open-almostunionfind/geninput.py b/kattis-open-almostunionfind/geninput.py
new file mode 100755
index 0000000..5eef1f3
--- /dev/null
+++ b/kattis-open-almostunionfind/geninput.py
@@ -0,0 +1,15 @@
+#!/usr/bin/python
+
+from random import randint as rand
+
+n, m = rand(10, 1000), rand(10, 1000)
+print(n, m)
+
+for _ in range(m):
+ t = rand(1, 3)
+ if t < 3:
+ p, q = rand(1, n), rand(1, n)
+ print(t, p, q)
+ else:
+ p = rand(1, n)
+ print(t, p)
diff --git a/kattis-open-almostunionfind/in2.txt b/kattis-open-almostunionfind/in2.txt
new file mode 100644
index 0000000..1bb97fe
--- /dev/null
+++ b/kattis-open-almostunionfind/in2.txt
@@ -0,0 +1,8 @@
+9 7
+1 6 1
+1 7 2
+1 5 2
+1 8 6
+1 5 8
+2 8 4
+3 5
diff --git a/kattis-open-almostunionfind/in3.txt b/kattis-open-almostunionfind/in3.txt
new file mode 100644
index 0000000..1a27497
--- /dev/null
+++ b/kattis-open-almostunionfind/in3.txt
@@ -0,0 +1,241 @@
+429 240
+3 245
+2 141 372
+1 300 23
+3 184
+1 91 179
+2 45 232
+1 203 425
+2 393 12
+1 399 339
+2 302 138
+2 204 132
+2 429 139
+3 233
+1 88 315
+1 59 318
+3 259
+2 173 166
+1 322 420
+1 72 386
+3 212
+3 417
+1 409 127
+3 118
+3 113
+2 89 208
+3 365
+2 79 406
+1 109 29
+1 385 59
+2 406 409
+1 29 297
+3 48
+1 211 297
+3 147
+2 24 161
+3 1
+3 130
+3 266
+2 338 92
+1 143 302
+2 317 367
+3 294
+2 401 220
+1 170 273
+3 25
+1 296 329
+1 255 214
+2 153 177
+2 228 55
+2 79 311
+2 374 51
+2 373 65
+2 386 35
+2 388 103
+1 429 395
+1 229 82
+1 62 416
+1 6 272
+3 81
+2 15 310
+1 414 375
+3 309
+1 122 259
+3 410
+3 6
+3 330
+2 201 390
+1 377 69
+3 310
+3 233
+2 157 246
+3 24
+2 168 108
+3 216
+2 282 5
+2 190 156
+3 427
+1 109 334
+3 37
+2 384 412
+1 324 74
+2 296 262
+3 412
+1 7 109
+2 31 317
+3 214
+1 55 164
+3 349
+3 202
+3 255
+1 27 278
+1 156 379
+2 429 328
+2 136 385
+1 199 188
+2 275 368
+3 164
+2 313 190
+2 324 182
+1 286 279
+3 311
+3 415
+2 330 146
+2 176 343
+2 281 20
+3 164
+3 134
+2 128 258
+1 258 335
+1 408 363
+1 413 110
+3 374
+1 31 28
+2 86 247
+3 416
+1 245 51
+3 27
+2 125 303
+1 111 227
+3 335
+3 305
+2 111 78
+2 411 77
+1 57 26
+3 425
+2 222 209
+3 251
+2 111 115
+3 328
+1 127 394
+1 89 387
+3 352
+3 346
+1 135 338
+3 407
+3 372
+2 51 41
+3 284
+2 153 411
+2 225 316
+1 180 257
+1 89 127
+3 150
+3 218
+2 242 249
+3 317
+1 371 83
+2 201 145
+3 336
+2 92 10
+1 199 18
+1 318 184
+2 333 306
+2 375 416
+2 198 245
+3 337
+3 331
+2 401 429
+1 239 260
+3 197
+1 89 421
+3 315
+2 219 91
+3 172
+1 56 273
+1 225 48
+1 89 238
+1 424 418
+1 162 296
+3 416
+2 376 265
+1 96 354
+2 55 326
+1 248 105
+1 425 247
+1 37 87
+2 166 254
+3 315
+3 80
+3 273
+1 191 139
+1 181 159
+2 135 158
+2 158 392
+2 179 84
+1 251 422
+1 152 218
+1 12 287
+2 47 330
+1 245 386
+2 199 423
+1 204 35
+2 6 227
+3 209
+3 98
+3 60
+3 79
+3 38
+3 417
+1 11 409
+1 23 151
+2 226 39
+3 173
+3 225
+2 92 376
+2 123 107
+1 331 60
+3 399
+2 96 249
+2 365 177
+1 410 325
+2 8 61
+2 5 199
+2 279 107
+2 303 329
+2 237 366
+2 91 335
+3 145
+3 52
+1 301 254
+3 395
+1 278 70
+1 233 341
+1 164 193
+3 365
+3 34
+3 50
+2 147 121
+3 278
+2 63 131
+2 328 87
+2 29 206
+1 320 238
+3 304
+2 183 414
+3 10
+2 178 8
+1 10 243
+3 20
+2 142 417
diff --git a/kattis-open-almostunionfind/input.txt b/kattis-open-almostunionfind/input.txt
new file mode 100644
index 0000000..315b418
--- /dev/null
+++ b/kattis-open-almostunionfind/input.txt
@@ -0,0 +1,41 @@
+17 40
+2 14 11
+2 3 13
+2 5 8
+2 13 15
+2 13 1
+2 4 6
+3 9
+2 2 7
+2 5 12
+2 14 1
+2 4 13
+3 6
+1 16 5
+3 12
+1 4 16
+1 15 3
+3 6
+3 3
+2 13 4
+3 16
+1 10 11
+3 6
+2 2 2
+3 4
+3 7
+3 3
+2 16 8
+2 7 2
+1 9 15
+3 14
+1 6 5
+2 17 3
+2 12 5
+3 17
+2 11 10
+3 2
+2 12 9
+1 17 2
+2 15 16
+1 3 15
diff --git a/kattis-open-almostunionfind/pyout.txt b/kattis-open-almostunionfind/pyout.txt
new file mode 100644
index 0000000..63fdad2
--- /dev/null
+++ b/kattis-open-almostunionfind/pyout.txt
@@ -0,0 +1,281 @@
+1 309
+1 500
+1 112
+1 142
+1 366
+1 575
+1 113
+1 126
+1 496
+1 349
+1 23
+1 103
+1 339
+1 30
+1 436
+1 311
+3 416
+1 184
+1 548
+1 561
+1 568
+1 45
+1 206
+1 329
+1 544
+1 478
+1 352
+1 555
+1 103
+2 1036
+1 541
+3 530
+4 1205
+2 723
+1 459
+1 453
+1 52
+1 74
+1 258
+1 11
+3 1435
+2 345
+1 411
+3 708
+1 100
+1 576
+1 277
+1 574
+2 650
+1 460
+1 316
+1 48
+1 164
+1 75
+2 638
+4 1205
+1 190
+1 496
+3 747
+1 466
+1 371
+1 558
+1 573
+2 927
+1 104
+2 563
+1 127
+1 311
+1 151
+2 932
+1 596
+1 187
+1 543
+2 93
+2 811
+1 154
+1 498
+6 2215
+1 248
+1 250
+1 548
+3 747
+1 47
+1 370
+2 992
+5 945
+1 292
+1 108
+1 327
+3 693
+2 992
+2 334
+2 334
+3 799
+2 784
+2 439
+5 1721
+1 231
+1 442
+1 377
+1 53
+2 658
+1 552
+4 1674
+3 958
+4 1674
+3 797
+4 1007
+1 22
+3 1231
+2 432
+3 1383
+1 475
+1 111
+2 1138
+2 686
+1 211
+3 918
+1 504
+2 177
+5 1941
+2 586
+1 507
+1 48
+1 332
+1 77
+17 5984
+1 364
+2 811
+2 500
+26 9440
+1 146
+2 500
+1 66
+1 537
+1 532
+1 74
+4 1540
+1 132
+1 405
+1 469
+3 385
+1 443
+4 1422
+3 1393
+1 11
+4 1422
+3 653
+4 892
+3 922
+2 737
+1 377
+1 232
+3 592
+1 128
+1 289
+1 452
+2 638
+2 986
+1 299
+2 439
+4 767
+1 120
+1 48
+2 214
+3 1393
+4 794
+2 500
+1 286
+2 932
+3 1311
+43 14918
+1 61
+2 584
+2 555
+1 63
+1 232
+2 742
+6 2007
+1 275
+1 75
+1 3
+4 1104
+2 1138
+1 73
+2 533
+4 1110
+1 299
+1 330
+17 4452
+6 1568
+4 1651
+5 802
+6 2007
+2 555
+1 354
+46 15564
+1 203
+11 3264
+1 249
+2 605
+1 338
+1 324
+7 2383
+3 1187
+1 510
+3 1018
+3 1176
+10 2671
+3 954
+2 439
+3 1187
+1 443
+57 18251
+59 18690
+1 578
+1 63
+2 492
+8 2710
+8 2710
+2 326
+2 326
+51 14428
+4 1479
+1 50
+65 21427
+1 228
+2 675
+1 362
+65 21556
+5 1683
+3 753
+2 477
+65 21556
+2 732
+5 1377
+51 14428
+51 14428
+1 528
+51 14225
+1 237
+2 932
+1 132
+7 1842
+5 1552
+64 21578
+1 458
+2 360
+3 555
+2 410
+51 14024
+1 407
+8 1910
+8 1910
+72 23820
+11 3914
+73 24655
+9 2532
+77 25911
+75 22332
+75 22332
+5 1377
+1 287
+1 200
+76 22868
+3 1031
+3 1041
+4 1244
+7 1468
+5 1525
+15 5005
+77 22896
+5 1466
+1 43
+3 781
+1 514
+7 1358
+2 1011
+1 374
+1 225
+7 1468
diff --git a/kattis-open-almostunionfind/rustout.txt b/kattis-open-almostunionfind/rustout.txt
new file mode 100644
index 0000000..63fdad2
--- /dev/null
+++ b/kattis-open-almostunionfind/rustout.txt
@@ -0,0 +1,281 @@
+1 309
+1 500
+1 112
+1 142
+1 366
+1 575
+1 113
+1 126
+1 496
+1 349
+1 23
+1 103
+1 339
+1 30
+1 436
+1 311
+3 416
+1 184
+1 548
+1 561
+1 568
+1 45
+1 206
+1 329
+1 544
+1 478
+1 352
+1 555
+1 103
+2 1036
+1 541
+3 530
+4 1205
+2 723
+1 459
+1 453
+1 52
+1 74
+1 258
+1 11
+3 1435
+2 345
+1 411
+3 708
+1 100
+1 576
+1 277
+1 574
+2 650
+1 460
+1 316
+1 48
+1 164
+1 75
+2 638
+4 1205
+1 190
+1 496
+3 747
+1 466
+1 371
+1 558
+1 573
+2 927
+1 104
+2 563
+1 127
+1 311
+1 151
+2 932
+1 596
+1 187
+1 543
+2 93
+2 811
+1 154
+1 498
+6 2215
+1 248
+1 250
+1 548
+3 747
+1 47
+1 370
+2 992
+5 945
+1 292
+1 108
+1 327
+3 693
+2 992
+2 334
+2 334
+3 799
+2 784
+2 439
+5 1721
+1 231
+1 442
+1 377
+1 53
+2 658
+1 552
+4 1674
+3 958
+4 1674
+3 797
+4 1007
+1 22
+3 1231
+2 432
+3 1383
+1 475
+1 111
+2 1138
+2 686
+1 211
+3 918
+1 504
+2 177
+5 1941
+2 586
+1 507
+1 48
+1 332
+1 77
+17 5984
+1 364
+2 811
+2 500
+26 9440
+1 146
+2 500
+1 66
+1 537
+1 532
+1 74
+4 1540
+1 132
+1 405
+1 469
+3 385
+1 443
+4 1422
+3 1393
+1 11
+4 1422
+3 653
+4 892
+3 922
+2 737
+1 377
+1 232
+3 592
+1 128
+1 289
+1 452
+2 638
+2 986
+1 299
+2 439
+4 767
+1 120
+1 48
+2 214
+3 1393
+4 794
+2 500
+1 286
+2 932
+3 1311
+43 14918
+1 61
+2 584
+2 555
+1 63
+1 232
+2 742
+6 2007
+1 275
+1 75
+1 3
+4 1104
+2 1138
+1 73
+2 533
+4 1110
+1 299
+1 330
+17 4452
+6 1568
+4 1651
+5 802
+6 2007
+2 555
+1 354
+46 15564
+1 203
+11 3264
+1 249
+2 605
+1 338
+1 324
+7 2383
+3 1187
+1 510
+3 1018
+3 1176
+10 2671
+3 954
+2 439
+3 1187
+1 443
+57 18251
+59 18690
+1 578
+1 63
+2 492
+8 2710
+8 2710
+2 326
+2 326
+51 14428
+4 1479
+1 50
+65 21427
+1 228
+2 675
+1 362
+65 21556
+5 1683
+3 753
+2 477
+65 21556
+2 732
+5 1377
+51 14428
+51 14428
+1 528
+51 14225
+1 237
+2 932
+1 132
+7 1842
+5 1552
+64 21578
+1 458
+2 360
+3 555
+2 410
+51 14024
+1 407
+8 1910
+8 1910
+72 23820
+11 3914
+73 24655
+9 2532
+77 25911
+75 22332
+75 22332
+5 1377
+1 287
+1 200
+76 22868
+3 1031
+3 1041
+4 1244
+7 1468
+5 1525
+15 5005
+77 22896
+5 1466
+1 43
+3 781
+1 514
+7 1358
+2 1011
+1 374
+1 225
+7 1468
diff --git a/kattis-open-almostunionfind/src/main.rs b/kattis-open-almostunionfind/src/main.rs
new file mode 100644
index 0000000..6563043
--- /dev/null
+++ b/kattis-open-almostunionfind/src/main.rs
@@ -0,0 +1,153 @@
+// https://open.kattis.com/problems/almostunionfind
+
+use std::{
+ io::{stdin, Read},
+ iter::once,
+};
+
+enum Node {
+ Root { count: u32, sum: u64 },
+ Child(usize),
+ Invalid,
+}
+
+impl Node {
+ fn count(&self) -> u32 {
+ match self {
+ &Root { count, .. } => count,
+ _ => unreachable!(),
+ }
+ }
+}
+
+use Node::*;
+
+fn root(uf: &mut [Node], mut node: usize) -> usize {
+ let mut root = node;
+ while let Child(parent) = uf[root] {
+ root = parent
+ }
+ while let Child(parent) = uf[node] {
+ uf[node] = Child(root);
+ node = parent;
+ }
+ root
+}
+
+fn join(uf: &mut [Node], a: usize, b: usize) {
+ let mut a = root(uf, a);
+ let mut b = root(uf, b);
+
+ if a == b {
+ return;
+ }
+
+ if uf[a].count() < uf[b].count() {
+ let tmp = a;
+ a = b;
+ b = tmp;
+ }
+
+ let (b_count, b_sum) = match uf[b] {
+ Root { count, sum } => (count, sum),
+ _ => unreachable!(),
+ };
+ match &mut uf[a] {
+ Root { count, sum } => {
+ *count += b_count;
+ *sum += b_sum;
+ }
+ _ => unreachable!(),
+ }
+ uf[b] = Child(a);
+}
+
+fn mov(
+ uf: &mut [Node],
+ free_index: &mut usize,
+ current_index_of: &mut [usize],
+ a: usize,
+ a_val: u64,
+ b: usize,
+) {
+ let a_root = root(uf, a);
+ let b_root = root(uf, b);
+ if a_root == b_root {
+ return;
+ }
+ match &mut uf[a_root] {
+ Root { count, sum } => {
+ *count -= 1;
+ *sum -= a_val;
+ }
+ _ => unreachable!(),
+ }
+ match &mut uf[b_root] {
+ Root { count, sum } => {
+ *count += 1;
+ *sum += a_val;
+ }
+ _ => unreachable!(),
+ }
+ uf[*free_index] = Child(b_root);
+ current_index_of[a_val as usize] = *free_index;
+ *free_index += 1;
+}
+
+fn main() {
+ let mut input = String::new();
+ stdin().lock().read_to_string(&mut input).unwrap();
+ let mut ints = input
+ .trim()
+ .split(|c| c == ' ' || c == '\n')
+ .map(|i| i.parse::<usize>().unwrap());
+ let mut get = || ints.next();
+
+ while let Some(n) = get() {
+ let m = get().unwrap();
+
+ let mut uf: Vec<Node> = (0..n + m)
+ .map(|i| {
+ if i < n {
+ Root {
+ count: 1,
+ sum: i as u64 + 1,
+ }
+ } else {
+ Invalid
+ }
+ })
+ .collect();
+ let mut free_index = n;
+ let mut current_index_of: Vec<usize> = (once(0).chain(0..n)).collect();
+
+ for _ in 0..m {
+ match get().unwrap() {
+ 1 => {
+ let (p, q) = (get().unwrap(), get().unwrap());
+ join(&mut uf, current_index_of[p], current_index_of[q]);
+ }
+ 2 => {
+ let (p, q) = (get().unwrap(), get().unwrap());
+ let (pi, qi) = (current_index_of[p], current_index_of[q]);
+ mov(
+ &mut uf,
+ &mut free_index,
+ &mut current_index_of,
+ pi,
+ p as u64,
+ qi,
+ );
+ }
+ _ => {
+ let p = get().unwrap();
+ let r = root(&mut uf, current_index_of[p]);
+ match uf[r] {
+ Root { count, sum } => println!("{} {}", count, sum),
+ _ => unreachable!(),
+ }
+ }
+ }
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-09-10 19:04:34 +0000