oj.uz

Submission #924433

# Submission time Handle Problem Language Result Execution time Memory
924433 2024-02-09T03:44:57 Z Muhammad_Aneeq Political Development (BOI17_politicaldevelopment) C++17
27 / 100
 3000 ms 5972 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int const N=6e4+10;
vector<int>nei[N]={};
int res[N]={};
int ans=0;
bool valid(vector<int>f)
{
    for (auto i:f)
        res[i]=0;
    for (auto i:f)
    {
        for (auto j:nei[i])
            res[j]++;
    }
    bool w=0;
    for (auto i:f)
    {
        if (res[i]!=f.size()-1)
        {
            w=1;
            break;
        }
    }
    return (!w);
}
vector<int>f;
int n,k;
void check(int j,int n)
{
    if (f.size()==k-1)
    {
        f.push_back(n);
        if (valid(f))
            ans=max(ans,int(f.size()));
        f.pop_back();
        return;
    }
    if (j==nei[n].size())
    {
        f.push_back(n);
        if (valid(f))
            ans=max(ans,int(f.size()));
        f.pop_back();
        return;
    }
    check(j+1,n);
    f.push_back(nei[n][j]);
    check(j+1,n);
    f.pop_back();
}
inline void solve()
{
    cin>>n>>k;
    for (int i=0;i<n;i++)
    {
        int d;
        cin>>d;
        while (d--)
        {
            int x;
            cin>>x;
            if (i!=x)
                nei[i].push_back(x);
        }
    }
    for (int i=1;i<=n;i++)
        check(0,i);
    cout<<min(ans,k)<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Compilation message

politicaldevelopment.cpp: In function 'bool valid(std::vector<int>)':
politicaldevelopment.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if (res[i]!=f.size()-1)
      |             ~~~~~~^~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void check(int, int)':
politicaldevelopment.cpp:39:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     if (f.size()==k-1)
      |         ~~~~~~~~^~~~~
politicaldevelopment.cpp:47:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if (j==nei[n].size())
      |         ~^~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 3 ms 2136 KB Output is correct
4 Correct 111 ms 2592 KB Output is correct
5 Correct 34 ms 2392 KB Output is correct
6 Correct 3 ms 1884 KB Output is correct
7 Correct 3 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 3 ms 2136 KB Output is correct
4 Correct 111 ms 2592 KB Output is correct
5 Correct 34 ms 2392 KB Output is correct
6 Correct 3 ms 1884 KB Output is correct
7 Correct 3 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 30 ms 2644 KB Output is correct
12 Execution timed out 3018 ms 2392 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 1808 ms 5956 KB Output is correct
12 Correct 1 ms 1624 KB Output is correct
13 Correct 1695 ms 5972 KB Output is correct
14 Correct 1 ms 1628 KB Output is correct
15 Correct 1723 ms 5956 KB Output is correct
16 Correct 1795 ms 5960 KB Output is correct
17 Correct 1795 ms 5960 KB Output is correct
18 Correct 1763 ms 5964 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 3 ms 2136 KB Output is correct
4 Correct 111 ms 2592 KB Output is correct
5 Correct 34 ms 2392 KB Output is correct
6 Correct 3 ms 1884 KB Output is correct
7 Correct 3 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 30 ms 2644 KB Output is correct
12 Execution timed out 3018 ms 2392 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1624 KB Output is correct
3 Correct 3 ms 2136 KB Output is correct
4 Correct 111 ms 2592 KB Output is correct
5 Correct 34 ms 2392 KB Output is correct
6 Correct 3 ms 1884 KB Output is correct
7 Correct 3 ms 1884 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 30 ms 2644 KB Output is correct
12 Execution timed out 3018 ms 2392 KB Time limit exceeded
13 Halted 0 ms 0 KB -