QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#151332 | #501. Subway | Mohammed_Atalah | 66 | 260ms | 4208kb | C++20 | 3.9kb | 2023-08-26 16:36:13 | 2023-08-26 16:36:15 |
Judging History
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();
}
}
詳細信息
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...