QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#792758 | #30. Political Development | seungni | 4 | 4ms | 6828kb | C++17 | 1.8kb | 2024-11-29 13:51:47 | 2024-11-29 13:51:50 |
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%