QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#199109#7514. Clique Challengeucup-team635WA 27ms5576kbRust3.9kb2023-10-03 21:10:162023-10-03 21:10:16

Judging History

你现在查看的是最新测评结果

  • [2023-10-03 21:10:16]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:5576kb
  • [2023-10-03 21:10:16]
  • 提交

answer

fn main() {
    input! {
        n: usize,
        m: usize,
        e: [(usize1, usize1); m],
    }
    let mut g = vec![vec![]; n];
    for (a, b) in e {
        g[a].push(b);
        g[b].push(a);
    }
    let mut used = vec![false; n];
    let mut ans = 0;
    let mut id = vec![n; n];
    for _ in 0..n {
        let x = (0..n)
            .filter(|x| !used[*x])
            .min_by_key(|x| g[*x].len())
            .unwrap();
        used[x] = true;
        let neighbor = std::mem::take(&mut g[x]);
        for (i, &v) in neighbor.iter().enumerate() {
            id[v] = i;
        }
        let mut graph = vec![0usize; neighbor.len()];
        for (i, (graph, &v)) in graph.iter_mut().zip(neighbor.iter()).enumerate() {
            g[v].retain(|p| *p != x);
            *graph |= 1 << i;
            for &u in g[v].iter() {
                let k = id[u];
                if k != n {
                    *graph |= 1 << k;
                }
            }
        }
        let m = neighbor.len() / 2;
        let (l, r) = graph.split_at(m);
        let mut and = vec![!0; 1 << r.len()];
        for (i, r) in r.iter().enumerate() {
            and[1 << i] = *r >> m;
        }
        bitwise_transform(&mut and, |a, b| *b &= *a);
        for (i, and) in and.iter_mut().enumerate() {
            if *and & i == i {
                *and = 1;
            } else {
                *and = 0;
            }
        }
        bitwise_transform(&mut and, |a, b| *b += *a);
        let memo = and;
        let mut and = vec![!0; 1 << l.len()];
        for (i, l) in l.iter().enumerate() {
            and[1 << i] = *l;
        }
        bitwise_transform(&mut and, |a, b| *b &= *a);
        for (i, and) in and.iter().enumerate() {
            if *and & i == i {
                ans += memo[*and >> m & (memo.len() - 1)];
            }
        }
        for &v in neighbor.iter() {
            id[v] = n;
        }
    }
    println!("{}", ans);
}

// ---------- begin bitwise transform ----------
pub fn bitwise_transform<T, F>(a: &mut [T], mut f: F)
where
    F: FnMut(&mut T, &mut T),
{
    let n = a.len().trailing_zeros() as usize;
    assert!(a.len() == 1 << n);
    for i in 0..n {
        for a in a.chunks_exact_mut(2 << i) {
            let (x, y) = a.split_at_mut(1 << i);
            for (x, y) in x.iter_mut().zip(y) {
                f(x, y);
            }
        }
    }
}
// ---------- end bitwise transform ----------
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 2216kb

input:

3 2
1 2
2 3

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 0ms
memory: 2296kb

input:

3 3
1 2
1 3
2 3

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 1ms
memory: 2088kb

input:

1000 100
446 789
167 547
254 777
777 185
33 446
777 847
185 877
757 167
72 383
847 446
254 478
959 185
757 446
847 959
959 167
757 847
747 757
446 167
989 757
547 777
33 747
33 254
254 843
33 547
446 980
877 205
185 72
980 959
33 205
877 757
33 847
478 843
757 478
167 877
72 789
877 959
980 478
167 ...

output:

1373

result:

ok single line: '1373'

Test #4:

score: 0
Accepted
time: 25ms
memory: 5392kb

input:

1000 1000
770 105
219 498
686 498
343 534
15 591
919 588
149 588
298 915
551 523
710 116
105 637
523 991
343 476
145 420
604 588
254 120
551 421
476 298
900 710
915 343
445 421
986 867
445 588
219 356
919 105
584 875
991 604
776 919
588 254
919 421
356 348
105 551
15 113
919 15
356 523
343 155
770 9...

output:

6621319

result:

ok single line: '6621319'

Test #5:

score: 0
Accepted
time: 27ms
memory: 5252kb

input:

1000 1000
840 251
559 572
77 993
857 254
176 77
30 423
838 251
862 466
920 254
254 593
593 423
780 575
487 865
952 176
480 77
351 487
620 390
231 496
423 761
993 385
383 390
220 620
862 805
920 838
77 339
838 231
691 384
930 251
840 77
593 993
838 930
176 761
383 761
480 487
251 383
295 390
289 808
...

output:

6403686

result:

ok single line: '6403686'

Test #6:

score: 0
Accepted
time: 18ms
memory: 5576kb

input:

1000 1000
179 73
322 80
586 342
73 819
973 184
508 131
351 342
576 179
397 23
523 926
684 73
479 722
973 80
576 397
301 508
903 618
672 192
33 903
973 885
523 661
885 8
787 988
647 990
393 211
722 586
751 926
960 322
179 131
131 988
196 342
508 351
672 342
644 926
990 819
301 80
73 397
104 131
678 3...

output:

6066915

result:

ok single line: '6066915'

Test #7:

score: 0
Accepted
time: 18ms
memory: 4068kb

input:

1000 1000
179 707
71 73
410 726
459 410
84 432
500 73
578 864
71 145
538 578
265 145
707 565
674 772
859 676
826 71
538 459
548 479
609 45
674 707
30 145
45 726
41 73
446 265
145 479
587 642
179 632
908 548
674 410
361 632
500 642
929 976
73 446
41 361
71 726
179 212
341 929
45 859
826 179
632 144
4...

output:

6242289

result:

ok single line: '6242289'

Test #8:

score: 0
Accepted
time: 18ms
memory: 3940kb

input:

1000 1000
146 917
487 589
225 927
972 449
969 728
99 288
615 564
728 146
880 561
563 745
442 880
118 392
634 564
636 917
442 738
280 254
225 710
254 449
221 564
394 969
556 99
634 589
976 301
117 487
561 867
98 880
392 880
917 819
556 634
941 969
653 927
972 615
146 819
969 98
653 941
809 699
590 30...

output:

9171879

result:

ok single line: '9171879'

Test #9:

score: 0
Accepted
time: 1ms
memory: 2156kb

input:

1000 1000
709 558
844 316
552 395
944 619
805 279
837 392
822 772
964 805
597 397
814 344
527 401
964 299
922 782
746 349
795 537
945 57
527 176
815 937
257 955
245 108
245 593
932 155
597 812
18 856
116 218
671 142
511 945
481 405
966 695
782 38
130 638
470 692
671 307
837 571
925 43
411 249
613 38...

output:

2186

result:

ok single line: '2186'

Test #10:

score: 0
Accepted
time: 1ms
memory: 2188kb

input:

1000 1000
833 350
567 76
488 416
350 135
874 275
555 996
263 152
14 380
409 442
672 836
490 5
421 901
781 875
135 209
162 442
6 47
111 180
317 162
876 368
393 656
712 535
583 976
918 591
29 887
436 599
702 5
512 778
901 111
423 591
274 599
686 655
2 656
444 172
836 800
865 920
3 19
781 375
157 683
8...

output:

2193

result:

ok single line: '2193'

Test #11:

score: 0
Accepted
time: 1ms
memory: 2140kb

input:

1000 1000
655 894
253 168
615 321
526 160
225 578
845 473
14 839
321 659
138 448
575 787
342 557
338 501
192 504
888 172
531 616
83 136
623 137
746 344
385 337
505 394
634 740
242 449
321 630
804 971
386 160
466 641
83 133
570 527
448 273
888 653
3 479
467 18
630 93
271 574
653 5
764 370
972 466
501...

output:

2159

result:

ok single line: '2159'

Test #12:

score: 0
Accepted
time: 1ms
memory: 2136kb

input:

1000 1000
210 626
59 74
95 486
328 63
894 222
908 764
299 197
871 600
954 241
431 660
816 997
186 34
737 604
889 568
454 115
61 933
417 221
279 971
333 340
143 374
168 409
426 50
875 423
86 413
805 719
222 319
461 864
244 679
49 220
98 579
329 737
568 926
328 330
694 445
318 480
576 748
242 989
968 ...

output:

2013

result:

ok single line: '2013'

Test #13:

score: 0
Accepted
time: 1ms
memory: 2088kb

input:

1000 1000
937 639
771 95
626 134
869 66
465 29
889 944
194 239
284 303
935 111
795 806
737 770
665 343
862 528
232 571
342 458
401 490
452 628
425 384
998 578
192 168
64 651
486 311
840 667
400 255
364 206
486 289
761 912
189 907
158 339
891 336
392 782
598 233
899 539
19 780
190 535
933 700
500 232...

output:

2004

result:

ok single line: '2004'

Test #14:

score: 0
Accepted
time: 1ms
memory: 2188kb

input:

1000 1000
568 607
217 544
12 124
766 801
924 290
957 218
816 552
913 189
982 916
896 289
304 74
426 190
844 543
849 972
386 59
626 472
869 838
234 581
232 707
623 685
873 344
295 496
352 557
314 35
329 432
155 422
803 322
42 735
36 760
249 306
706 533
748 161
887 911
872 64
440 450
662 607
274 659
7...

output:

2002

result:

ok single line: '2002'

Test #15:

score: 0
Accepted
time: 0ms
memory: 2260kb

input:

1000 1000
726 492
65 652
168 218
347 489
35 415
73 324
80 419
237 352
378 3
708 286
933 810
116 563
819 610
670 386
392 940
434 926
341 617
820 842
618 974
592 344
724 578
955 761
26 902
545 496
688 636
273 225
749 840
661 784
917 595
503 84
414 252
925 877
352 479
792 914
54 666
324 257
642 637
801...

output:

2002

result:

ok single line: '2002'

Test #16:

score: 0
Accepted
time: 1ms
memory: 2308kb

input:

1000 1000
344 107
264 268
28 38
211 260
741 682
654 885
607 213
610 296
869 556
685 269
996 929
61 370
804 605
786 570
41 448
104 549
245 166
36 84
265 135
704 409
60 299
895 645
868 140
3 483
448 341
778 460
930 13
796 688
936 751
808 458
859 502
918 43
920 287
680 976
918 172
378 156
962 834
635 3...

output:

2002

result:

ok single line: '2002'

Test #17:

score: 0
Accepted
time: 1ms
memory: 2096kb

input:

1000 1000
117 152
117 375
190 586
117 586
278 546
788 450
117 90
511 586
450 595
586 492
870 278
17 117
586 275
520 471
796 117
520 112
117 431
292 520
320 520
278 95
586 677
450 402
298 520
586 109
450 409
520 607
684 278
520 898
340 278
17 520
586 64
586 100
520 647
450 270
520 617
685 117
117 985...

output:

6290

result:

ok single line: '6290'

Test #18:

score: 0
Accepted
time: 1ms
memory: 2164kb

input:

1000 1000
88 346
534 200
881 661
869 23
35 869
26 785
158 785
881 981
835 881
88 466
88 559
760 88
905 869
869 672
869 256
945 534
881 664
905 30
631 868
536 124
869 271
712 88
534 30
513 785
785 902
491 869
869 868
505 869
488 897
905 144
88 513
785 536
785 599
303 905
534 869
158 897
384 905
236 9...

output:

132867

result:

ok single line: '132867'

Test #19:

score: 0
Accepted
time: 2ms
memory: 2328kb

input:

1000 1000
463 338
246 242
91 76
130 858
818 250
255 639
135 571
809 250
794 255
91 170
386 678
639 513
507 684
463 407
463 969
463 769
685 463
250 513
126 684
684 444
53 969
250 876
811 639
286 571
386 684
571 407
794 463
507 463
295 170
678 809
91 678
811 349
777 53
463 286
261 401
130 346
91 625
8...

output:

9143208

result:

ok single line: '9143208'

Test #20:

score: -100
Wrong Answer
time: 9ms
memory: 2484kb

input:

1000 1000
624 79
120 926
418 455
310 792
116 165
688 185
34 792
985 129
884 79
624 847
356 494
79 785
15 891
792 455
274 554
891 518
453 116
792 188
356 57
884 669
926 940
608 673
847 884
884 455
871 985
418 15
185 926
871 608
78 145
554 494
356 669
129 792
624 129
274 79
284 129
688 116
940 650
884...

output:

1119880117

result:

wrong answer 1st lines differ - expected: '119880110', found: '1119880117'