QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#792758#30. Political Developmentseungni4 4ms6828kbC++171.8kb2024-11-29 13:51:472024-11-29 13:51:50

Judging History

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

  • [2024-11-29 13:51:50]
  • 评测
  • 测评结果:4
  • 用时:4ms
  • 内存:6828kb
  • [2024-11-29 13:51:47]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N, K, ans;
set<int> graph[50005];
int ok[50005];

void DFS(int root, int now, int state, int k) {
    ans = max(ans, k);
    if (now == graph[root].size()) return;
    int idx = 0, nxt = -1;
    for (auto i: graph[now]) {
        if (idx == now) {
            nxt = i;
            break;
        }
        idx++;
    }
    
    DFS(root, now + 1, state, k);
    int flag = 0;
    idx = 0;
    for (auto i: graph[now]) {
        if (state & (1 << idx)) {
            if (!graph[nxt].count(i)) {
                flag = 1;
                break;
            }
        }
        idx++;
    }
    if (!flag) DFS(root, now + 1, state | (1 << now), k + 1);
    return;
}

void solve() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int a;
            cin >> a;
            graph[i].insert(a);
        }
    }
    
    set<pii> s;
    for (int i = 0; i < N; i++) {
        s.insert({graph[i].size(), i});
    }
    
    while (s.size()) {
        pii now = *s.begin();
        if (ok[now.second]) s.erase(now);
        else {
            DFS(now.second, 0, 0, 1);
            for (auto i: graph[now.second]) {
                s.erase({graph[i].size(), i});
                graph[i].erase(now.second);
            }
            for (auto i: graph[now.second]) s.insert({graph[i].size(), i});
            ok[now.second] = 1;
        }
    }
    
    cout << ans;
    
    return;
}

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 4
Accepted

Test #1:

score: 4
Accepted
time: 1ms
memory: 6020kb

input:

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

output:

2

result:

ok single line: '2'

Test #2:

score: 4
Accepted
time: 0ms
memory: 6164kb

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: 4
Accepted
time: 2ms
memory: 6604kb

input:

5000 2
1 1791
1 4343
2 2031 1630
1 286
2 4788 1978
3 847 2364 4193
2 88 1614
1 3321
1 1441
1 1098
1 1547
1 318
1 4939
1 697
3 1335 3973 2092
1 3700
1 3959
1 4582
2 2907 3324
1 364
1 4868
1 1406
4 1827 3291 2215 4513
2 1303 2448
3 3699 2272 775
4 3113 1333 2670 1991
2 2450 3615
4 3825 2008 1100 2938
...

output:

2

result:

ok single line: '2'

Test #4:

score: 4
Accepted
time: 4ms
memory: 6600kb

input:

5000 2
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460
1 1460...

output:

2

result:

ok single line: '2'

Test #5:

score: 4
Accepted
time: 0ms
memory: 6792kb

input:

5000 2
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782
1 1782...

output:

2

result:

ok single line: '2'

Test #6:

score: 4
Accepted
time: 4ms
memory: 6536kb

input:

5000 2
1 1692
1 3670
1 3770
1 2722
1 2554
1 4972
1 3203
1 1406
1 62
1 2411
1 4472
1 3565
1 1465
1 4734
1 3229
1 707
1 4925
1 597
1 3764
1 1406
1 778
1 2086
1 1696
1 2956
1 707
1 1406
1 3604
1 597
1 1275
1 3203
1 707
1 4577
1 997
1 3604
1 1747
1 860
1 3565
1 3693
1 164
1 818
1 3693
1 4790
1 86
1 3969...

output:

2

result:

ok single line: '2'

Test #7:

score: 4
Accepted
time: 4ms
memory: 6628kb

input:

5000 2
1 1495
1 4736
1 2861
72 2890 4002 3751 2434 4908 3707 1698 4275 2507 2625 1942 1452 1309 2552 4 3667 4794 289 309 3334 2996 3208 1001 2408 707 3200 4272 3343 4465 4748 1352 48 2894 4367 3534 4594 4433 4265 3168 2324 2681 4909 1986 501 2958 784 4138 409 2837 4999 3840 3654 327 3620 4399 319 33...

output:

2

result:

ok single line: '2'

Test #8:

score: 4
Accepted
time: 2ms
memory: 6132kb

input:

5000 2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

1

result:

ok single line: '1'

Test #9:

score: 4
Accepted
time: 0ms
memory: 5868kb

input:

1 1
0

output:

1

result:

ok single line: '1'

Test #10:

score: 4
Accepted
time: 2ms
memory: 6140kb

input:

5000 2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

2

result:

ok single line: '2'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #11:

score: 12
Accepted
time: 4ms
memory: 6684kb

input:

5000 2
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154
1 1154...

output:

2

result:

ok single line: '2'

Test #12:

score: 12
Accepted
time: 4ms
memory: 6632kb

input:

5000 3
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423
1 1423...

output:

2

result:

ok single line: '2'

Test #13:

score: 12
Accepted
time: 1ms
memory: 5880kb

input:

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

output:

2

result:

ok single line: '2'

Test #14:

score: 12
Accepted
time: 0ms
memory: 6632kb

input:

5000 3
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937
1 2937...

output:

2

result:

ok single line: '2'

Test #15:

score: 12
Accepted
time: 1ms
memory: 6160kb

input:

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

output:

3

result:

ok single line: '3'

Test #16:

score: 12
Accepted
time: 4ms
memory: 6828kb

input:

5000 3
1 2124
1 3797
1 4553
1 4508
1 1597
1 1937
1 4085
1 72
1 1579
1 4933
1 4085
1 4553
1 1759
1 3797
1 1579
1 2531
1 4297
1 814
1 3729
1 4070
1 1606
1 1251
1 920
1 1365
1 3586
1 2124
1 827
1 4132
1 4645
1 3586
1 3945
1 72
1 4933
1 1759
1 1365
1 3729
1 1759
1 2531
1 2715
1 1817
1 494
1 1937
1 3489
...

output:

2

result:

ok single line: '2'

Test #17:

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

input:

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

output:

2

result:

wrong answer 1st lines differ - expected: '3', found: '2'

Subtask #3:

score: 0
Wrong Answer

Test #44:

score: 23
Accepted
time: 2ms
memory: 6160kb

input:

5000 4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

output:

1

result:

ok single line: '1'

Test #45:

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

input:

20 6
5 16 14 9 18 1
4 15 19 0 7
5 15 8 17 5 12
5 15 16 12 6 13
5 12 18 10 5 9
5 16 4 6 2 8
5 3 16 5 18 8
5 13 17 19 11 1
5 6 2 5 18 10
5 15 4 0 12 11
5 4 14 8 13 17
4 15 9 13 7
5 3 4 14 2 9
5 3 10 19 7 11
5 12 10 17 19 0
5 3 9 1 2 11
5 3 6 0 19 5
5 14 2 18 10 7
5 4 6 8 17 0
5 16 14 13 1 7

output:

2

result:

wrong answer 1st lines differ - expected: '3', found: '2'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #2:

0%