oj.uz

Submission #1079479

# Submission time Handle Problem Language Result Execution time Memory
1079479 2024-08-28T15:36:56 Z andrei_iorgulescu Political Development (BOI17_politicaldevelopment) C++14
100 / 100
 364 ms 316752 KB 
#include <bits/stdc++.h>

using namespace std;

int n,k;
bitset<50005> bs[50005];
vector<int> g[50005];
int deg[50005];
bool luat[50005];
int cn;
vector<int> o;
bool iau[15];
int ans = 1;

void afis()
{
    int ctt = 0;
    for (int i = 0; i < o.size(); i++)
        if (iau[i])
            ctt++;
    for (int i = 0; i < o.size(); i++)
        for (int j = i + 1; j < o.size(); j++)
            if (iau[i] and iau[j] and !bs[o[i]][o[j]])
                return;
    ans = max(ans, 1 + ctt);
}

void bkt(int pos)
{
    if (pos == o.size())
        afis();
    else
    {
        iau[pos] = false;
        bkt(pos + 1);
        iau[pos] = true;
        bkt(pos + 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int cati;
        cin >> cati;
        while (cati--)
        {
            int x;
            cin >> x;
            g[i].push_back(x);
            bs[i][x] = 1;
        }
    }
    set<pair<int,int>> cmn;
    for (int i = 0; i < n; i++)
    {
        deg[i] = g[i].size();
        cmn.insert({deg[i], i});
    }
    while (!cmn.empty())
    {
        pair<int,int> pr = *cmn.begin();
        cmn.erase(pr);
        luat[pr.second] = true;
        for (auto vec : g[pr.second])
        {
            if (!luat[vec])
            {
                cmn.erase({deg[vec], vec});
                deg[vec]--;
                cmn.insert({deg[vec], vec});
            }
        }
        vector<int> oameni;
        for (auto it : g[pr.second])
            if (!luat[it])
                oameni.push_back(it);
        o = oameni;
        cn = pr.second;
        bkt(0);
    }
    cout << ans;
    return 0;
}

Compilation message

politicaldevelopment.cpp: In function 'void afis()':
politicaldevelopment.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < o.size(); i++)
      |                     ~~^~~~~~~~~~
politicaldevelopment.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < o.size(); i++)
      |                     ~~^~~~~~~~~~
politicaldevelopment.cpp:22:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int j = i + 1; j < o.size(); j++)
      |                             ~~^~~~~~~~~~
politicaldevelopment.cpp: In function 'void bkt(int)':
politicaldevelopment.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     if (pos == o.size())
      |         ~~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 9 ms 26204 KB Output is correct
4 Correct 8 ms 25248 KB Output is correct
5 Correct 9 ms 25232 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 9 ms 25288 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 9 ms 26204 KB Output is correct
4 Correct 8 ms 25248 KB Output is correct
5 Correct 9 ms 25232 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 9 ms 25288 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 9 ms 25948 KB Output is correct
12 Correct 9 ms 25176 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 11 ms 23132 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 10 ms 23900 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 9 ms 22360 KB Output is correct
21 Correct 8 ms 22996 KB Output is correct
22 Correct 2 ms 4788 KB Output is correct
23 Correct 11 ms 23408 KB Output is correct
24 Correct 2 ms 4952 KB Output is correct
25 Correct 15 ms 24156 KB Output is correct
26 Correct 12 ms 22876 KB Output is correct
27 Correct 11 ms 24156 KB Output is correct
28 Correct 12 ms 23524 KB Output is correct
29 Correct 9 ms 24408 KB Output is correct
30 Correct 12 ms 23388 KB Output is correct
31 Correct 16 ms 24440 KB Output is correct
32 Correct 12 ms 23360 KB Output is correct
33 Correct 13 ms 24408 KB Output is correct
34 Correct 13 ms 24388 KB Output is correct
35 Correct 5 ms 13144 KB Output is correct
36 Correct 5 ms 12380 KB Output is correct
37 Correct 6 ms 13032 KB Output is correct
38 Correct 6 ms 7256 KB Output is correct
39 Correct 4 ms 8024 KB Output is correct
40 Correct 15 ms 24664 KB Output is correct
41 Correct 3 ms 7772 KB Output is correct
42 Correct 15 ms 24764 KB Output is correct
43 Correct 14 ms 24668 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 364 ms 316552 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 319 ms 316752 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 331 ms 316500 KB Output is correct
16 Correct 332 ms 316752 KB Output is correct
17 Correct 329 ms 316500 KB Output is correct
18 Correct 326 ms 316500 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 9 ms 26204 KB Output is correct
4 Correct 8 ms 25248 KB Output is correct
5 Correct 9 ms 25232 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 9 ms 25288 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 9 ms 25948 KB Output is correct
12 Correct 9 ms 25176 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 11 ms 23132 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 10 ms 23900 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 9 ms 22360 KB Output is correct
21 Correct 8 ms 22996 KB Output is correct
22 Correct 2 ms 4788 KB Output is correct
23 Correct 11 ms 23408 KB Output is correct
24 Correct 2 ms 4952 KB Output is correct
25 Correct 15 ms 24156 KB Output is correct
26 Correct 12 ms 22876 KB Output is correct
27 Correct 11 ms 24156 KB Output is correct
28 Correct 12 ms 23524 KB Output is correct
29 Correct 9 ms 24408 KB Output is correct
30 Correct 12 ms 23388 KB Output is correct
31 Correct 16 ms 24440 KB Output is correct
32 Correct 12 ms 23360 KB Output is correct
33 Correct 13 ms 24408 KB Output is correct
34 Correct 13 ms 24388 KB Output is correct
35 Correct 5 ms 13144 KB Output is correct
36 Correct 5 ms 12380 KB Output is correct
37 Correct 6 ms 13032 KB Output is correct
38 Correct 6 ms 7256 KB Output is correct
39 Correct 4 ms 8024 KB Output is correct
40 Correct 15 ms 24664 KB Output is correct
41 Correct 3 ms 7772 KB Output is correct
42 Correct 15 ms 24764 KB Output is correct
43 Correct 14 ms 24668 KB Output is correct
44 Correct 32 ms 26200 KB Output is correct
45 Correct 1 ms 2392 KB Output is correct
46 Correct 14 ms 25692 KB Output is correct
47 Correct 20 ms 25288 KB Output is correct
48 Correct 15 ms 23900 KB Output is correct
49 Correct 21 ms 25372 KB Output is correct
50 Correct 22 ms 25448 KB Output is correct
51 Correct 49 ms 26124 KB Output is correct
52 Correct 10 ms 22360 KB Output is correct
53 Correct 56 ms 26460 KB Output is correct
54 Correct 76 ms 26484 KB Output is correct
55 Correct 11 ms 23132 KB Output is correct
56 Correct 9 ms 23144 KB Output is correct
57 Correct 1 ms 2648 KB Output is correct
58 Correct 54 ms 27400 KB Output is correct
59 Correct 12 ms 25436 KB Output is correct
60 Correct 10 ms 24920 KB Output is correct
61 Correct 11 ms 25436 KB Output is correct
62 Correct 11 ms 25560 KB Output is correct
63 Correct 26 ms 26460 KB Output is correct
64 Correct 21 ms 25944 KB Output is correct
65 Correct 13 ms 25692 KB Output is correct
66 Correct 13 ms 25272 KB Output is correct
67 Correct 25 ms 26716 KB Output is correct
68 Correct 19 ms 26460 KB Output is correct
69 Correct 13 ms 25688 KB Output is correct
70 Correct 17 ms 25948 KB Output is correct
71 Correct 23 ms 26716 KB Output is correct
72 Correct 26 ms 25908 KB Output is correct
73 Correct 11 ms 24668 KB Output is correct
74 Correct 17 ms 25944 KB Output is correct
75 Correct 21 ms 26716 KB Output is correct
76 Correct 15 ms 26204 KB Output is correct
77 Correct 31 ms 26576 KB Output is correct
78 Correct 11 ms 25368 KB Output is correct
79 Correct 13 ms 14820 KB Output is correct
80 Correct 15 ms 26204 KB Output is correct
81 Correct 37 ms 26940 KB Output is correct
82 Correct 3 ms 9052 KB Output is correct
83 Correct 14 ms 14940 KB Output is correct
84 Correct 24 ms 26724 KB Output is correct
85 Correct 2 ms 8540 KB Output is correct
86 Correct 24 ms 26716 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 9 ms 26204 KB Output is correct
4 Correct 8 ms 25248 KB Output is correct
5 Correct 9 ms 25232 KB Output is correct
6 Correct 10 ms 25180 KB Output is correct
7 Correct 9 ms 25288 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 9 ms 25948 KB Output is correct
12 Correct 9 ms 25176 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 10 ms 23900 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 11 ms 23132 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 10 ms 23900 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 9 ms 22360 KB Output is correct
21 Correct 8 ms 22996 KB Output is correct
22 Correct 2 ms 4788 KB Output is correct
23 Correct 11 ms 23408 KB Output is correct
24 Correct 2 ms 4952 KB Output is correct
25 Correct 15 ms 24156 KB Output is correct
26 Correct 12 ms 22876 KB Output is correct
27 Correct 11 ms 24156 KB Output is correct
28 Correct 12 ms 23524 KB Output is correct
29 Correct 9 ms 24408 KB Output is correct
30 Correct 12 ms 23388 KB Output is correct
31 Correct 16 ms 24440 KB Output is correct
32 Correct 12 ms 23360 KB Output is correct
33 Correct 13 ms 24408 KB Output is correct
34 Correct 13 ms 24388 KB Output is correct
35 Correct 5 ms 13144 KB Output is correct
36 Correct 5 ms 12380 KB Output is correct
37 Correct 6 ms 13032 KB Output is correct
38 Correct 6 ms 7256 KB Output is correct
39 Correct 4 ms 8024 KB Output is correct
40 Correct 15 ms 24664 KB Output is correct
41 Correct 3 ms 7772 KB Output is correct
42 Correct 15 ms 24764 KB Output is correct
43 Correct 14 ms 24668 KB Output is correct
44 Correct 1 ms 2396 KB Output is correct
45 Correct 233 ms 308912 KB Output is correct
46 Correct 145 ms 280980 KB Output is correct
47 Correct 233 ms 307720 KB Output is correct
48 Correct 244 ms 308820 KB Output is correct
49 Correct 98 ms 209644 KB Output is correct
50 Correct 198 ms 314960 KB Output is correct
51 Correct 239 ms 307540 KB Output is correct
52 Correct 91 ms 196436 KB Output is correct
53 Correct 107 ms 208856 KB Output is correct
54 Correct 10 ms 4956 KB Output is correct
55 Correct 219 ms 314784 KB Output is correct
56 Correct 96 ms 193616 KB Output is correct
57 Correct 101 ms 194896 KB Output is correct
58 Correct 154 ms 293980 KB Output is correct
59 Correct 90 ms 193092 KB Output is correct
60 Correct 89 ms 193876 KB Output is correct
61 Correct 140 ms 293968 KB Output is correct
62 Correct 139 ms 265812 KB Output is correct
63 Correct 172 ms 288096 KB Output is correct
64 Correct 88 ms 193752 KB Output is correct
65 Correct 202 ms 298580 KB Output is correct
66 Correct 137 ms 266008 KB Output is correct
67 Correct 172 ms 287572 KB Output is correct
68 Correct 186 ms 296788 KB Output is correct
69 Correct 214 ms 297552 KB Output is correct
70 Correct 128 ms 265292 KB Output is correct
71 Correct 185 ms 296788 KB Output is correct
72 Correct 154 ms 278872 KB Output is correct
73 Correct 213 ms 309840 KB Output is correct
74 Correct 126 ms 265716 KB Output is correct
75 Correct 89 ms 144720 KB Output is correct
76 Correct 148 ms 271712 KB Output is correct
77 Correct 214 ms 309844 KB Output is correct
78 Correct 101 ms 150352 KB Output is correct
79 Correct 94 ms 145236 KB Output is correct
80 Correct 33 ms 60244 KB Output is correct
81 Correct 97 ms 150340 KB Output is correct
82 Correct 180 ms 305492 KB Output is correct
83 Correct 36 ms 59736 KB Output is correct
84 Correct 186 ms 305236 KB Output is correct