QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#151332#501. SubwayMohammed_Atalah66 260ms4208kbC++203.9kb2023-08-26 16:36:132023-08-26 16:36:15

Judging History

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

  • [2023-08-26 16:36:15]
  • 评测
  • 测评结果:66
  • 用时:260ms
  • 内存:4208kb
  • [2023-08-26 16:36:13]
  • 提交

answer

/// Template path: /home/mohammed/.config/sublime-text-3/Packages/User

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

// typedef
typedef long long ll;
typedef long double ld;
typedef vector<int> vecint;
typedef vector<char> vecchar;
typedef vector<string> vecstr;
typedef vector<long long> vecll;

// Marcos
#define endl ("\n")
#define int long long
#define mod 1000000007
#define pi (3.141592653589)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = a; i > b; i--)
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

// Functions
long long squared(long long x) { return (x * x) % mod; }
int factorial(int n)
{
    long long res = 1;
    for (int i = 1; i <= n; i++)
    {
        res = ((res * i) % mod + mod) % mod;
    }
    return res;
}
long long power(long long x, long long p)
{
    if (p == 0)
    {
        return 1;
    }
    if (p % 2 == 1)
    {
        return (power(x, p - 1) * x) % mod;
    }
    return squared(power(x, p / 2));
}

// cout << fixed;
// cout << setprecision(4);

// ---------(^_^)--------- //

// vector<vector<int>> check_new(1000, vector<int>(1000, 0));
map<int, map<int, int>> check_new;
vector<vector<int>> edg;

vector<int> vis;
bool e = 0;
vector<vector<int>> to_del;
vector<vector<int>> result1;
vector<vector<int>> result2;
void dfs(int idx, int parent)
{
    if (e)
        return;
    for (auto &i : edg[idx])
    {
        if (vis[i] && i != parent && check_new[i][idx] != -2 && !e)
        {
            e = 1;
            check_new[to_del[0][0]][to_del[0][1]] = -2;
            check_new[to_del[0][1]][to_del[0][0]] = -2;
            result1.push_back({to_del[0][0], to_del[0][1]});
            return;
        }
        else if (vis[i] || check_new[i][idx] == -2)
        {
            continue;
        }
        else
        {
            vis[i] = 1;
            if (check_new[idx][i] == -1)
            {
                to_del.push_back({idx, i});
            }
            dfs(i, idx);
            if (check_new[idx][i] == -1 && !e)
            {
                to_del.pop_back();
            }
            vis[i] = 0;
        }
    }
}

void main_solve()
{

    int n;
    cin >> n;

    edg.resize(n);
    vis.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        check_new[a][b] = -1;
        check_new[b][a] = -1;
        edg[a].push_back(b);
        edg[b].push_back(a);
    }
    vector<vector<int>> nw;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        if (check_new[a][b] == -1)
        {
            check_new[a][b] = 1;
            check_new[b][a] = 1;
            continue;
        }
        nw.push_back({a, b});
    }
    for (int i = 0; i < nw.size(); i++)
    {

        int a = nw[i][0];
        int b = nw[i][1];
        // cout << check_new[4][7] << endl;
        // cout << a << ' ' << b << "  " << check_new[a][b] << endl;

        e = 0;
        vis.clear();
        to_del.clear();
        vis.resize(n);
        check_new[a][b] = 1;
        check_new[b][a] = 1;
        edg[a].push_back(b);
        edg[b].push_back(a);
        vis[a] = 1;
        dfs(a, a);
        result2.push_back({a, b});
    }

    int o = result1.size();
    cout << o << endl;
    for (int i = 0; i < o; i++)
    {
        cout << result1[i][0] << " ";
        cout << result1[i][1] << " ";
        cout << result2[i][0] << " ";
        cout << result2[i][1] << " ";
        cout << endl;
    }
}

int32_t main()
{

    fast;
    // #ifndef ONLINE_JUDGE
    // 	freopen("input.txt", "r", stdin);
    // 	freopen("output.txt", "w", stdout);
    // #endif
    // Just another problem (-_-)

    int t;
    t = 1;
    // cin >> t;

    while (t--)
    {
        main_solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 33
Accepted

Test #1:

score: 33
Accepted
time: 1ms
memory: 3456kb

input:

10
3 9
0 2
0 6
5 2
8 7
8 1
9 5
2 8
4 7
8 9
1 2
6 1
9 4
5 9
7 1
9 3
4 7
1 0

output:

6
8 2 8 9 
1 8 1 2 
6 0 6 1 
8 7 9 4 
5 2 7 1 
2 0 1 0 

result:

ok correct plan

Test #2:

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

input:

10
3 9
1 3
9 2
6 3
3 4
7 5
0 9
8 6
3 5
7 6
1 8
5 4
7 0
3 4
5 7
4 9
8 5
2 4

output:

7
5 3 7 6 
1 3 1 8 
6 3 5 4 
3 9 7 0 
0 9 4 9 
8 6 8 5 
2 9 2 4 

result:

ok correct plan

Test #3:

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

input:

10
9 0
5 6
3 7
2 9
0 4
8 9
2 1
1 5
4 7
6 9
9 0
6 2
7 5
8 1
4 8
3 7
9 3
1 7

output:

7
6 5 6 9 
9 2 6 2 
7 4 7 5 
8 9 8 1 
4 0 4 8 
2 1 9 3 
1 5 1 7 

result:

ok correct plan

Test #4:

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

input:

10
9 8
4 6
6 1
9 2
6 9
5 8
7 3
0 6
6 3
7 8
9 8
4 2
3 9
8 2
2 6
2 1
2 5
6 0

output:

7
7 3 7 8 
4 6 4 2 
3 6 3 9 
9 2 8 2 
9 6 2 6 
6 1 2 1 
8 5 2 5 

result:

ok correct plan

Test #5:

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

input:

10
6 4
5 7
6 8
8 1
9 5
0 9
5 6
8 2
5 3
9 0
6 1
0 8
9 2
7 1
3 4
8 5
0 4
6 4

output:

7
6 8 6 1 
9 5 0 8 
8 2 9 2 
7 5 7 1 
3 5 3 4 
8 1 8 5 
5 6 0 4 

result:

ok correct plan

Test #6:

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

input:

10
3 0
4 8
5 2
1 7
8 1
1 9
9 6
5 1
0 1
3 5
6 7
5 4
7 1
3 9
5 2
7 8
2 0
5 1

output:

6
3 0 3 5 
6 9 6 7 
1 8 5 4 
1 9 3 9 
4 8 7 8 
1 0 2 0 

result:

ok correct plan

Test #7:

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

input:

10
6 0
7 9
3 2
8 4
5 0
7 8
1 4
2 8
8 6
0 6
9 6
7 1
1 8
8 3
3 2
7 5
4 9
2 4

output:

7
9 7 9 6 
7 8 7 1 
1 4 1 8 
8 2 8 3 
8 6 7 5 
4 8 4 9 
5 0 2 4 

result:

ok correct plan

Test #8:

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

input:

10
8 0
8 9
6 5
6 1
4 1
2 4
3 5
7 9
7 2
1 8
9 4
4 1
0 7
7 2
7 5
3 4
7 4
6 7

output:

7
4 2 1 8 
9 8 9 4 
0 8 0 7 
7 9 7 5 
3 5 3 4 
5 6 7 4 
6 1 6 7 

result:

ok correct plan

Test #9:

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

input:

10
4 7
2 7
9 1
5 9
8 5
8 3
1 6
2 0
0 3
5 7
2 7
1 0
1 3
3 6
6 4
9 0
8 2
8 4

output:

8
5 8 5 7 
1 9 1 0 
0 3 1 3 
1 6 3 6 
0 2 6 4 
9 5 9 0 
8 3 8 2 
7 4 8 4 

result:

ok correct plan

Test #10:

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

input:

10
1 7
3 1
2 1
1 4
0 1
8 1
6 1
5 1
1 9
5 8
9 4
1 2
2 9
3 0
3 6
0 2
8 0
1 7

output:

7
5 1 5 8 
9 1 9 4 
1 4 2 9 
3 1 3 0 
0 1 3 6 
6 1 0 2 
8 1 8 0 

result:

ok correct plan

Test #11:

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

input:

10
0 3
6 3
3 2
5 3
3 7
9 3
3 8
4 3
3 1
4 9
2 9
1 7
1 0
6 0
6 5
3 7
8 2
8 5

output:

8
4 3 4 9 
2 3 2 9 
1 3 1 7 
3 0 1 0 
6 3 6 0 
3 5 6 5 
8 3 8 2 
9 3 8 5 

result:

ok correct plan

Test #12:

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

input:

10
9 0
3 6
1 2
5 0
7 2
5 3
4 3
2 8
9 2
3 2
1 2
2 8
9 2
5 2
2 4
2 6
2 0
2 7

output:

5
3 5 3 2 
5 0 5 2 
3 4 2 4 
3 6 2 6 
9 0 2 0 

result:

ok correct plan

Test #13:

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

input:

10
7 3
7 2
6 9
9 4
0 4
5 0
1 6
2 8
5 8
1 8
0 8
8 7
8 6
8 5
4 8
8 9
2 8
3 8

output:

7
1 6 1 8 
0 5 0 8 
2 7 8 7 
0 4 8 6 
4 9 4 8 
6 9 8 9 
3 7 3 8 

result:

ok correct plan

Test #14:

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

input:

10
1 0
3 1
6 1
8 1
1 9
5 1
1 2
7 1
1 4
3 4
3 8
0 3
5 3
7 3
3 1
9 3
3 6
3 2

output:

8
1 4 3 4 
1 8 3 8 
0 1 0 3 
5 1 5 3 
7 1 7 3 
9 1 9 3 
1 6 3 6 
1 2 3 2 

result:

ok correct plan

Subtask #2:

score: 33
Accepted

Dependency #1:

100%
Accepted

Test #15:

score: 33
Accepted
time: 174ms
memory: 4108kb

input:

1000
348 567
932 737
892 211
384 728
788 48
788 701
113 693
462 13
835 576
716 109
673 924
333 570
718 262
688 383
297 837
505 217
370 480
123 271
282 85
707 126
508 276
855 604
75 291
914 775
186 144
69 346
662 173
183 323
637 452
233 588
794 720
374 768
514 621
873 573
316 13
985 260
503 762
319 7...

output:

996
386 60 386 191 
683 19 683 515 
375 931 375 639 
827 599 827 125 
832 23 832 835 
229 233 229 575 
976 441 976 612 
799 94 799 322 
667 882 667 181 
445 41 445 371 
475 233 475 86 
202 794 202 535 
165 299 165 239 
250 252 250 413 
926 505 926 945 
575 715 229 116 
534 295 534 753 
610 262 610 5...

result:

ok correct plan

Test #16:

score: 0
Accepted
time: 163ms
memory: 4028kb

input:

1000
248 518
429 949
91 664
763 207
685 789
76 904
545 668
343 616
678 119
161 607
873 373
250 903
280 728
929 333
840 261
387 94
420 417
658 892
725 770
452 536
471 873
597 90
870 474
877 411
510 619
469 419
950 910
724 740
752 531
578 731
53 199
832 572
691 411
709 595
590 787
590 387
174 401
400 ...

output:

998
934 182 934 257 
170 857 170 659 
105 649 105 791 
486 309 486 715 
909 466 909 794 
412 517 412 839 
623 186 623 827 
45 842 45 990 
31 20 31 893 
414 661 414 399 
237 636 237 744 
546 878 546 65 
79 744 79 166 
291 152 291 158 
804 890 804 764 
776 204 776 934 
744 579 744 827 
172 810 172 318...

result:

ok correct plan

Test #17:

score: 0
Accepted
time: 168ms
memory: 4060kb

input:

1000
764 335
731 61
57 480
554 880
191 41
176 647
216 230
835 270
830 160
27 698
453 508
295 345
628 3
326 692
899 215
886 667
28 945
597 592
694 912
30 657
634 9
796 76
599 517
740 821
194 343
190 320
202 931
156 336
76 221
48 59
73 75
685 347
715 987
828 479
540 649
893 143
308 618
329 860
618 987...

output:

996
338 139 338 341 
219 746 219 644 
9 359 9 975 
357 42 357 734 
884 453 884 380 
589 222 589 796 
754 987 754 210 
885 884 885 284 
614 703 614 272 
668 753 668 491 
82 600 82 826 
165 548 165 241 
818 97 818 999 
515 75 515 117 
447 124 447 515 
998 82 998 236 
170 888 170 176 
456 46 456 564 
6...

result:

ok correct plan

Test #18:

score: 0
Accepted
time: 170ms
memory: 4060kb

input:

1000
67 288
409 23
779 637
530 714
711 815
784 568
14 267
167 865
569 714
215 725
682 541
354 808
727 712
455 524
704 189
774 533
310 250
689 145
10 676
430 631
488 887
38 939
931 767
49 299
908 224
737 558
896 292
623 420
100 907
418 483
274 952
198 645
532 347
555 395
414 535
2 721
733 46
655 366
...

output:

996
192 291 192 7 
405 346 405 440 
695 100 695 252 
377 356 377 16 
862 136 862 802 
877 966 877 397 
379 354 379 165 
283 448 283 438 
117 787 117 245 
667 904 667 444 
203 346 203 465 
324 628 324 670 
825 508 825 384 
498 372 498 679 
925 509 925 57 
152 615 152 728 
453 28 453 265 
401 676 401 ...

result:

ok correct plan

Test #19:

score: 0
Accepted
time: 171ms
memory: 4020kb

input:

1000
902 649
471 295
444 855
973 83
934 588
813 812
705 714
727 338
739 920
4 296
999 736
279 194
388 525
939 362
459 859
691 716
211 106
855 253
712 763
234 591
394 400
20 973
773 612
143 642
125 190
121 824
131 549
23 626
478 428
883 391
339 730
400 462
337 242
361 432
184 706
922 606
964 897
297 ...

output:

998
576 874 576 805 
767 779 767 884 
125 699 125 639 
171 522 171 768 
236 517 236 944 
69 327 69 513 
695 148 695 128 
488 400 488 635 
258 525 258 141 
919 365 919 887 
318 723 318 301 
17 415 17 487 
619 892 619 393 
923 854 923 341 
727 866 727 923 
348 282 348 307 
832 785 832 812 
145 79 145 ...

result:

ok correct plan

Test #20:

score: 0
Accepted
time: 165ms
memory: 4100kb

input:

1000
555 882
983 29
807 358
339 801
405 125
592 37
775 539
393 416
826 183
183 411
337 61
963 558
498 294
948 992
399 992
670 899
945 974
944 705
858 49
588 828
790 283
519 495
101 97
882 783
237 176
279 473
26 301
568 742
401 604
636 964
651 938
650 417
506 829
444 23
140 39
898 428
291 261
58 48
1...

output:

995
721 592 721 449 
397 49 397 374 
41 32 41 488 
578 403 578 203 
655 909 655 877 
943 496 943 159 
48 58 48 500 
508 828 508 617 
345 368 345 9 
86 751 86 133 
604 401 604 449 
28 880 28 174 
802 20 802 713 
709 548 709 518 
417 650 417 284 
875 240 875 518 
212 830 212 219 
143 11 143 53 
690 64...

result:

ok correct plan

Test #21:

score: 0
Accepted
time: 170ms
memory: 4148kb

input:

1000
418 478
890 45
965 387
912 152
956 968
560 552
4 872
53 685
1 191
430 687
109 580
525 898
862 673
155 98
766 576
726 310
407 916
286 928
776 326
1 359
395 107
701 295
21 381
311 849
934 971
638 256
676 634
445 283
541 788
365 335
822 651
508 995
851 244
621 798
940 587
564 236
234 652
519 747
9...

output:

997
815 658 815 534 
699 345 699 39 
942 797 942 741 
228 704 228 96 
481 736 481 913 
117 895 117 769 
826 293 826 615 
812 34 812 613 
524 963 524 147 
842 606 842 996 
282 982 282 442 
584 912 584 413 
358 978 358 803 
985 385 985 164 
30 83 30 791 
834 655 834 179 
785 318 785 934 
614 171 614 4...

result:

ok correct plan

Test #22:

score: 0
Accepted
time: 179ms
memory: 4188kb

input:

1000
507 495
444 258
539 49
239 657
887 708
527 366
521 994
510 942
684 595
697 219
266 133
667 148
59 410
227 550
344 492
73 250
741 96
386 425
568 39
168 17
213 248
642 69
885 293
612 384
642 65
596 653
557 525
365 465
971 399
507 974
692 590
347 316
463 81
398 889
341 126
866 703
629 36
64 379
67...

output:

997
243 903 243 855 
821 579 821 782 
175 570 175 434 
138 829 138 299 
740 440 740 22 
51 275 51 386 
865 319 865 86 
949 846 949 398 
402 290 402 404 
809 215 809 853 
842 114 842 700 
886 480 886 308 
578 499 578 320 
50 563 50 582 
146 408 146 504 
755 0 755 908 
640 434 640 710 
404 609 402 129...

result:

ok correct plan

Test #23:

score: 0
Accepted
time: 193ms
memory: 4136kb

input:

1000
433 547
577 473
670 990
71 68
338 641
898 718
671 430
139 337
100 585
522 689
151 586
901 907
740 616
324 377
444 344
949 592
723 766
623 792
688 607
51 680
915 619
428 312
454 737
621 638
312 233
160 163
418 281
501 699
318 306
852 433
961 594
812 244
50 816
67 49
914 848
342 463
672 750
94 41...

output:

995
705 241 705 184 
529 8 529 672 
665 301 665 913 
604 454 604 461 
439 162 439 966 
595 574 595 880 
475 981 475 398 
399 932 399 95 
782 295 782 523 
978 588 978 68 
691 330 691 552 
840 57 840 628 
75 374 437 258 
828 63 828 689 
163 160 163 958 
721 548 721 819 
404 466 404 634 
907 32 907 593...

result:

ok correct plan

Test #24:

score: 0
Accepted
time: 210ms
memory: 4040kb

input:

1000
872 593
593 40
404 593
593 477
373 593
299 593
552 593
593 549
593 770
504 593
593 233
283 593
593 439
305 593
593 861
248 593
593 206
593 969
986 593
63 593
507 593
593 592
593 801
593 832
16 593
155 593
593 249
282 593
584 593
593 76
593 528
90 593
589 593
199 593
593 397
871 593
593 854
593 ...

output:

996
44 593 44 8 
269 593 269 401 
526 593 526 71 
785 593 785 989 
444 593 444 495 
362 593 362 164 
706 593 706 719 
509 593 509 81 
752 593 752 682 
693 593 693 473 
403 593 403 719 
753 593 753 288 
140 593 140 174 
896 593 896 941 
987 593 987 953 
940 593 940 537 
278 593 278 460 
124 593 124 8...

result:

ok correct plan

Test #25:

score: 0
Accepted
time: 210ms
memory: 4148kb

input:

1000
934 596
596 198
596 856
707 596
824 596
894 596
57 596
596 48
596 239
966 596
528 596
596 752
733 596
596 134
596 458
596 651
751 596
596 852
956 596
596 343
596 868
782 596
596 723
596 223
396 596
596 488
30 596
466 596
596 182
596 255
596 690
400 596
42 596
154 596
596 418
286 596
596 132
596...

output:

997
838 596 838 785 
152 596 152 883 
189 596 189 784 
917 596 917 92 
541 596 541 691 
902 596 902 913 
749 596 749 304 
794 596 794 542 
361 596 361 271 
38 596 38 146 
2 596 2 805 
675 596 675 179 
559 596 559 382 
405 596 405 580 
582 596 582 669 
599 596 599 829 
605 596 605 463 
502 596 502 85...

result:

ok correct plan

Test #26:

score: 0
Accepted
time: 259ms
memory: 4040kb

input:

1000
282 471
947 855
481 957
794 163
581 522
746 952
104 526
96 290
109 479
890 260
800 346
155 449
979 640
649 512
771 714
843 890
352 410
344 300
661 214
357 755
277 184
211 327
51 547
778 308
789 40
926 324
796 615
821 555
886 326
414 670
808 792
188 218
147 980
420 323
880 945
332 411
941 709
48...

output:

998
488 599 3 815 
770 517 770 3 
815 461 3 168 
901 789 901 3 
168 328 3 314 
314 413 3 441 
441 228 3 304 
804 587 804 3 
698 406 698 3 
613 663 613 3 
785 625 785 3 
304 898 3 426 
426 953 3 826 
991 987 991 3 
148 826 148 3 
148 800 3 531 
189 846 189 3 
90 384 90 3 
531 821 3 492 
492 473 3 319...

result:

ok correct plan

Test #27:

score: 0
Accepted
time: 260ms
memory: 4208kb

input:

1000
82 430
580 433
691 424
629 677
733 32
452 289
377 85
90 595
757 16
431 689
641 953
305 11
37 721
686 723
235 845
348 544
527 112
120 44
868 331
649 105
412 217
682 585
65 313
616 600
682 987
574 697
857 364
255 504
907 435
403 82
434 826
482 78
925 741
49 505
191 10
728 38
734 840
676 794
975 6...

output:

997
676 626 794 279 
285 615 285 794 
279 255 794 289 
988 69 794 982 
735 621 735 794 
653 729 653 794 
200 944 200 794 
648 437 648 794 
367 101 367 794 
289 462 794 851 
982 438 794 937 
766 473 766 794 
285 378 794 478 
388 917 388 794 
241 445 241 794 
851 593 794 799 
478 506 794 133 
653 340 ...

result:

ok correct plan

Test #28:

score: 0
Accepted
time: 254ms
memory: 4064kb

input:

1000
331 742
331 349
93 331
331 313
858 331
186 331
331 79
963 331
331 655
794 331
331 708
331 617
331 825
816 331
331 972
331 433
331 386
151 331
331 65
26 331
331 507
331 827
874 331
331 763
754 331
331 326
542 331
317 331
411 331
843 331
331 581
499 331
331 294
731 331
350 331
331 377
331 716
331...

output:

998
331 172 917 172 
331 732 917 732 
328 331 328 917 
331 330 917 330 
374 331 374 917 
312 331 312 917 
949 331 949 917 
331 880 917 880 
331 811 917 811 
708 331 708 917 
489 331 489 917 
779 331 779 917 
331 874 917 874 
331 32 917 32 
783 331 783 917 
331 161 917 161 
551 331 551 917 
754 331 7...

result:

ok correct plan

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #29:

score: 0
Time Limit Exceeded

input:

100000
33519 47565
15314 53925
97473 1294
36181 203
43153 35817
58834 26736
43152 5273
22424 166
86386 66765
75443 48628
30114 12540
46832 27287
73603 21140
32869 18413
2014 89450
38832 53165
85305 53036
83805 59517
53057 81534
75703 48997
83131 49629
24487 27605
87629 2272
18872 98522
19385 42486
3...

output:


result: