QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290736#30. Political Developmentjames1BadCreeper0 6ms5916kbC++141.6kb2023-12-25 11:25:352023-12-25 11:25:36

Judging History

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

  • [2023-12-25 11:25:36]
  • 评测
  • 测评结果:0
  • 用时:6ms
  • 内存:5916kb
  • [2023-12-25 11:25:35]
  • 提交

answer

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

int n, m, d[50005], del[50005], ans = 1;
vector<int> G[50005], tmp; 
map<pair<int, int>, bool> M;
bool is[50005]; 

bool dfs(void){
    for (int i = 0; i < tmp.size(); i++)
        if (is[i] == 0) {
            is[i] = 1;
            for (int j = 0; j < i; j++)
                is[j] = 0; 
            return true;
        }
    return false;
}
void solve(void) {
    #define pii pair<int, int> 
    priority_queue<pii, vector<pii>, greater<pii>> q; 
    for (int i = 0; i < n; i++) q.emplace(0, i); 
    while (!q.empty()) {
        int now = q.top().second; q.pop(); 
        if (del[now]) continue; del[now] = 1; 
        tmp.clear(); 
        for (int u : G[now]) {
            if (!del[u]) tmp.push_back(u); 
            q.emplace(0, u); 
        }
        while (dfs()) {
            bool ok = 1; 
            vector<int> chs;
            for (int i = 0; i < tmp.size(); i++)
                if (is[i])
                    chs.push_back(tmp[i]);
            for (int i = 0; i < chs.size(); i++)
                for (int j = i + 1; j < chs.size(); j++)
                    if (!M[{chs[i], chs[j]}]) { ok = 0; goto ed; }
        ed:
            if (ok)
                ans = max(ans, (int)chs.size() + 1);
        }
        for (int i = 0; i < tmp.size(); ++i) is[i] = 0; 
    }
}
int main(void) {
    scanf("%d%d", &n, &m); 
    for (int i = 0; i < n; ++i) {
        int K; scanf("%d", &K);
        while (K--) {
            int x, y = i; scanf("%d", &x); 
            G[x].push_back(y); ++d[y]; M[{x, y}] = 1; 
        }
    }
    solve(); 
    return !printf("%d\n", ans); 
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

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

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: 0
Accepted
time: 1ms
memory: 4976kb

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: 0
Accepted
time: 6ms
memory: 5916kb

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
Time Limit Exceeded

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:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #44:

score: 23
Accepted
time: 0ms
memory: 4988kb

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
Accepted
time: 1ms
memory: 4924kb

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:

3

result:

ok single line: '3'

Test #46:

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

input:

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

output:

3

result:

ok single line: '3'

Test #47:

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

input:

13 5
2 11 12
2 11 2
3 7 6 1
2 11 6
2 11 7
2 11 10
3 2 7 3
3 2 6 4
3 10 12 9
2 11 8
3 8 12 5
6 5 9 0 1 4 3
3 10 8 0

output:

3

result:

ok single line: '3'

Test #48:

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

input:

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

output:

5

result:

ok single line: '5'

Test #49:

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

input:

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

output:

5

result:

ok single line: '5'

Test #50:

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

input:

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

output:

5

result:

ok single line: '5'

Test #51:

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

input:

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

output:

4

result:

ok single line: '4'

Test #52:

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

input:

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

output:

5

result:

ok single line: '5'

Test #53:

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

input:

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

output:

4

result:

ok single line: '4'

Test #54:

score: -23
Time Limit Exceeded

input:

50000 10
9 32960 26666 36698 27825 19469 40251 7694 43050 49699
9 28680 11214 13759 31209 6922 20079 42730 11997 443
9 4366 42847 15773 31538 6839 18130 22993 45787 37886
9 29348 35251 38031 35020 29149 1972 33352 38984 8565
9 115 2566 8766 22339 44559 33816 38982 39958 14757
9 25095 44878 9405 3414...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #2:

0%