QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290736 | #30. Political Development | james1BadCreeper | 0 | 6ms | 5916kb | C++14 | 1.6kb | 2023-12-25 11:25:35 | 2023-12-25 11:25:36 |
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%