QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#534151#5493. 程序自动分析ancienta40 1563ms82768kbC++203.2kb2024-08-26 21:13:062024-08-26 21:13:07

Judging History

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

  • [2024-08-26 21:13:07]
  • 评测
  • 测评结果:40
  • 用时:1563ms
  • 内存:82768kb
  • [2024-08-26 21:13:06]
  • 提交

answer

#include <iostream>
#include <map>
#include <queue>
using namespace std;
#define LL long long
int main()
{
    LL t;
    cin >> t;
    for (int x = 0; x < t; ++x)
    {
        LL n;
        cin >> n;
        map<LL, queue<LL>> equal;
        queue<LL> inquiry_a, inquiry_b;
        map<LL, LL> value;
        for (int i = 0; i < n; ++i)
        {
            LL a, b, c;
            cin >> a >> b >> c;
            if (1 == c) // equal
            {
                map<LL, queue<LL>> :: iterator it = equal.find(a);
                if (it == equal.end())
                {
                    queue<LL> q;
                    q.push(b);
                    equal.insert({a, q});
                }
                else
                {
                    equal[a].push(b);
                }
                it = equal.find(b);
                if (it == equal.end())
                {
                    queue<LL> q;
                    q.push(a);
                    equal.insert({b, q});
                }
                else
                {
                    equal[a].push(a);
                }
            }
            else // inquiry
            {
                inquiry_a.push(a);
                inquiry_b.push(b);
            }
        }
        LL index = 0ll;
        for (auto const& [first, second] : equal)
        {
            map<LL, LL> :: iterator it = value.find(first);
            if (it == value.end())
            {
                index ++;
                queue<LL> q;
                q.push(first);
                while (!q.empty())
                {
                    LL a = q.front();
                    q.pop();
                    value.insert({a, index});
                    map<LL, queue<LL>> :: iterator it2 = equal.find(a);
                    if (it2 != equal.end())
                    {
                        while (!it2->second.empty())
                        {
                            LL b = it2->second.front();
                            it2->second.pop();
                            if (value.find(b) == value.end())
                            {
                                q.push(b);
                            }
                        }
                    }
                }
            }
        }
        /*for (auto const& [first, second] : value)
        {
            cout << first << " " << second << endl;
        }*/
        bool result = true;
        while (!inquiry_a.empty())
        {
            LL a = inquiry_a.front();
            inquiry_a.pop();
            LL b = inquiry_b.front();
            inquiry_b.pop();
            if (a == b)
            {
                result = false;
                continue;
            }
            if (value.find(a) == value.end() || value.find(b) == value.end())
            {
                continue;
            }
            else
            {
                if (value[a] == value[b]) result = false;
            }
        }
        if (result)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3588kb

input:

5
2
1 2 1
1 2 0
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0
2
1 2 1
2 1 1
1
1 1 1

output:

NO
YES
NO
YES
YES

result:

ok 5 lines

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3528kb

input:

10
1
1 2 1
1
2 2 0
10
1 2 1
2 3 1
3 5 1
5 10 1
10 100 1
10000 100 1
1 9999 0
3 2 1
10000 1 0
2 3 1
4
1 7 1
9 7 0
13 9 1
1 13 1
5
7 9 0
9 7 0
3 5 0
1 7 0
2 4 0
9
24 234 1
2837 1 1
235 877 1
242 78 0
23 1 1
223 977 0
254 76 1
235 987 0
877 987 1
9
24 234 1
2837 1 1
242 78 0
23 1 1
223 977 0
254 76 1
2...

output:

YES
NO
YES
NO
YES
NO
YES
NO
YES
YES

result:

wrong answer 3rd lines differ - expected: 'NO', found: 'YES'

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 3644kb

input:

10
100
3039 366 1
608 1142 1
9794 4263 1
7148 6719 1
5824 9205 1
2757 6158 1
6183 298 1
4420 4418 1
4420 5600 0
4049 3039 1
7232 1799 1
9211 8516 1
398 389 1
4 8846 1
4492 571 1
6796 8019 1
603 571 1
575 837 1
389 1547 1
6195 8096 1
9906 6158 1
8846 9622 1
2964 571 1
9062 6119 1
7460 9719 1
5098 807...

output:

NO
YES
YES
YES
YES
YES
NO
YES
YES
YES

result:

wrong answer 8th lines differ - expected: 'NO', found: 'YES'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 3884kb

input:

10
100
1547 7716 1
1733 8724 1
1621 5578 1
5578 3189 1
4519 3434 1
9216 4070 1
4764 5986 1
4534 9641 1
5520 8252 1
4029 3189 1
4012 1136 1
3602 5520 1
757 2121 1
3807 1088 1
9216 5578 1
8507 3620 1
4534 1088 1
4899 8252 1
4899 1941 1
3602 8451 1
438 7214 1
1547 4012 1
2121 5791 1
5105 8451 1
1887 55...

output:

YES
YES
YES
YES
YES
NO
YES
YES
NO
YES

result:

wrong answer 3rd lines differ - expected: 'NO', found: 'YES'

Test #5:

score: 0
Wrong Answer
time: 11ms
memory: 4436kb

input:

10
1000
3951 3499 1
4458 5015 1
800 8958 1
702 4627 1
2052 7089 1
2456 4892 1
8683 9389 1
3922 2187 1
8170 3272 1
76 200 1
2567 2078 1
58 4897 1
8742 6328 1
8506 2462 1
1610 3150 1
9244 8025 1
7390 5968 1
4897 5015 1
2841 4592 1
2541 7630 1
7482 1157 1
2337 6156 1
4271 2349 1
2412 1750 1
8366 6196 1...

output:

YES
NO
YES
YES
YES
NO
YES
YES
YES
YES

result:

wrong answer 1st lines differ - expected: 'NO', found: 'YES'

Test #6:

score: 0
Wrong Answer
time: 112ms
memory: 8296kb

input:

10
10000
4967 5731 1
1154 4083 1
2643 9044 1
853 8116 1
1725 9222 1
975 7335 1
9579 8430 1
5832 6293 1
2621 9227 1
9620 8784 1
5617 4373 1
3185 774 1
3296 7952 1
6871 2143 1
8646 3606 1
1140 1859 1
6872 456 1
8619 2807 1
7935 6361 1
6768 1318 1
9112 3672 1
4064 9323 1
6200 2306 1
7524 5447 1
1408 87...

output:

NO
NO
NO
NO
YES
NO
YES
NO
YES
NO

result:

wrong answer 7th lines differ - expected: 'NO', found: 'YES'

Test #7:

score: 10
Accepted
time: 6ms
memory: 4900kb

input:

10
1000
3607 6465 0
521 2274 0
8200 9210 0
5196 2370 0
7465 4838 0
215 6017 0
4681 5522 0
5239 1520 0
642 6258 0
2045 4894 0
1372 8333 0
7373 8456 0
1520 852 0
3908 2874 0
2158 697 0
9496 1751 0
8931 1124 0
9833 856 0
9247 9274 0
7676 3965 0
7821 2948 0
4822 4070 0
4383 8764 0
3067 3248 0
6505 4906 ...

output:

YES
NO
YES
YES
YES
NO
NO
YES
YES
YES

result:

ok 10 lines

Test #8:

score: 10
Accepted
time: 606ms
memory: 11772kb

input:

10
10000
5011 61 1
655 7926 1
9936 8349 1
6592 9678 1
2392 351 1
8674 8909 1
3479 7449 1
3541 5836 1
5958 4624 1
9755 2747 1
4444 8176 1
2339 8121 1
4868 9472 1
3132 8411 1
7864 2746 1
7800 8634 1
6866 7629 1
8558 5817 1
5004 1223 1
1520 7 1
4244 518 1
2124 7571 1
6876 9547 1
8604 3411 1
6241 8852 1...

output:

YES
YES
YES
YES
NO
YES
NO
NO
NO
NO

result:

ok 10 lines

Test #9:

score: 10
Accepted
time: 937ms
memory: 33424kb

input:

10
10000
2561 174 1
352 195 1
2456 998 1
6403 8398 1
3457 2250 1
603 4352 1
5509 415 1
1230 3575 1
4826 1335 1
1429 4836 1
6290 6211 1
6531 5533 1
3713 1549 1
5809 8575 1
1530 7098 1
4002 8133 1
708 5738 1
5069 4560 1
5740 6281 1
5968 2393 1
2293 9033 1
1164 8924 1
4393 3788 1
1474 6615 1
1773 4275 ...

output:

YES
YES
YES
NO
NO
YES
NO
NO
NO
NO

result:

ok 10 lines

Test #10:

score: 0
Wrong Answer
time: 1563ms
memory: 82768kb

input:

10
100000
1 2 1
3 4 1
5 6 0
7 8 0
9 10 1
11 12 0
13 14 0
15 16 0
17 18 0
19 20 0
21 22 1
23 24 1
25 26 1
27 28 1
29 30 1
31 32 1
33 34 1
35 36 0
37 38 1
39 40 0
41 42 1
43 44 0
45 46 0
47 48 1
49 50 0
51 52 0
53 54 1
55 56 0
57 58 0
59 60 1
61 62 1
63 64 0
65 66 1
67 68 0
69 70 1
71 72 0
73 74 1
75 ...

output:

YES
YES
YES
YES
NO
YES
YES
NO
NO
YES

result:

wrong answer 6th lines differ - expected: 'NO', found: 'YES'