oj.uz

Submission #129112

# Submission time Handle Problem Language Result Execution time Memory
129112 2019-07-11T17:01:02 Z davitmarg Political Development (BOI17_politicaldevelopment) C++17
4 / 100
 117 ms 1968 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,k,used[50004],c[50004],ind[50004],s[50004],f[(1<<11)+5],ans=1;
vector<int> g[50004];
queue<int> q;

int main()
{
	cin>>n>>k;
    for(int i=0;i<n;i++)
	{
        int d,to;
        cin>>d;
        while(d--)
		{
            scanf("%d",&to);
            g[i].PB(to);
		}
		s[i]=g[i].size();
	}

    for(int i=1;i<(1<<k);i++)
	{
        for(int j=k-1;j>=0;j--)
			if(i&(1<<j))
			{
				f[i]=j;
                c[i]++;
			}
	}

    for(int i=0;i<n;i++)
        if(s[i]<k)
            q.push(i);

    while(!q.empty())
	{
        int v=q.front();
        q.pop();
        used[v]=1;
        vector<int> a,mask;
        for(int i=0;i<g[v].size();i++)
		{
			int to=g[v][i];
			s[to]--;
			if(!used[to])
			{
				if(s[to]==k-1)
					q.push(to);
				a.PB(to);
			}
		}

        for(int i=0;i<a.size();i++)
            ind[a[i]]=i;

        mask.resize(a.size());
        for(int i=0;i<a.size();i++)
            for(int j=0;j<g[a[i]].size();j++)
			{
				int to=g[a[i]][j];
                if(!used[to])
                    mask[i]|=(1<<ind[to]);
			}

        vector<int> dp((1<<k)+10);
        dp[0]=1;
        for(int m=1;m<(1<<a.size());m++)
        {
            if((((1<<f[m])^m)&(mask[f[m]]))==((1<<f[m])^m) && dp[m^(1<<f[m])])
			{
                dp[m]=1;
                ans=max(ans,c[m]+1);
			}
        }
	}
	cout<<ans<<endl;
	return 0;
}


/*

5 4
4 1 2 3 4
3 0 2 3
3 0 1 3
3 0 1 2
1 0

*/

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[v].size();i++)
                     ~^~~~~~~~~~~~
politicaldevelopment.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<a.size();i++)
                     ~^~~~~~~~~
politicaldevelopment.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<a.size();i++)
                     ~^~~~~~~~~
politicaldevelopment.cpp:81:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<g[a[i]].size();j++)
                         ~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&to);
             ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 8 ms 1784 KB Output is correct
4 Correct 116 ms 1784 KB Output is correct
5 Correct 116 ms 1884 KB Output is correct
6 Correct 9 ms 1784 KB Output is correct
7 Correct 9 ms 1916 KB Output is correct
8 Correct 5 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 4 ms 1528 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 8 ms 1784 KB Output is correct
4 Correct 116 ms 1784 KB Output is correct
5 Correct 116 ms 1884 KB Output is correct
6 Correct 9 ms 1784 KB Output is correct
7 Correct 9 ms 1916 KB Output is correct
8 Correct 5 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 4 ms 1528 KB Output is correct
11 Correct 113 ms 1848 KB Output is correct
12 Correct 117 ms 1832 KB Output is correct
13 Correct 3 ms 1428 KB Output is correct
14 Correct 115 ms 1968 KB Output is correct
15 Correct 3 ms 1500 KB Output is correct
16 Correct 10 ms 1784 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 9 ms 1912 KB Output is correct
19 Correct 5 ms 1528 KB Output is correct
20 Correct 6 ms 1784 KB Output is correct
21 Correct 6 ms 1784 KB Output is correct
22 Correct 5 ms 1656 KB Output is correct
23 Correct 9 ms 1784 KB Output is correct
24 Correct 5 ms 1528 KB Output is correct
25 Correct 8 ms 1784 KB Output is correct
26 Incorrect 8 ms 1784 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1528 KB Output is correct
2 Incorrect 3 ms 1528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 8 ms 1784 KB Output is correct
4 Correct 116 ms 1784 KB Output is correct
5 Correct 116 ms 1884 KB Output is correct
6 Correct 9 ms 1784 KB Output is correct
7 Correct 9 ms 1916 KB Output is correct
8 Correct 5 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 4 ms 1528 KB Output is correct
11 Correct 113 ms 1848 KB Output is correct
12 Correct 117 ms 1832 KB Output is correct
13 Correct 3 ms 1428 KB Output is correct
14 Correct 115 ms 1968 KB Output is correct
15 Correct 3 ms 1500 KB Output is correct
16 Correct 10 ms 1784 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 9 ms 1912 KB Output is correct
19 Correct 5 ms 1528 KB Output is correct
20 Correct 6 ms 1784 KB Output is correct
21 Correct 6 ms 1784 KB Output is correct
22 Correct 5 ms 1656 KB Output is correct
23 Correct 9 ms 1784 KB Output is correct
24 Correct 5 ms 1528 KB Output is correct
25 Correct 8 ms 1784 KB Output is correct
26 Incorrect 8 ms 1784 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1528 KB Output is correct
3 Correct 8 ms 1784 KB Output is correct
4 Correct 116 ms 1784 KB Output is correct
5 Correct 116 ms 1884 KB Output is correct
6 Correct 9 ms 1784 KB Output is correct
7 Correct 9 ms 1916 KB Output is correct
8 Correct 5 ms 1528 KB Output is correct
9 Correct 3 ms 1528 KB Output is correct
10 Correct 4 ms 1528 KB Output is correct
11 Correct 113 ms 1848 KB Output is correct
12 Correct 117 ms 1832 KB Output is correct
13 Correct 3 ms 1428 KB Output is correct
14 Correct 115 ms 1968 KB Output is correct
15 Correct 3 ms 1500 KB Output is correct
16 Correct 10 ms 1784 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 9 ms 1912 KB Output is correct
19 Correct 5 ms 1528 KB Output is correct
20 Correct 6 ms 1784 KB Output is correct
21 Correct 6 ms 1784 KB Output is correct
22 Correct 5 ms 1656 KB Output is correct
23 Correct 9 ms 1784 KB Output is correct
24 Correct 5 ms 1528 KB Output is correct
25 Correct 8 ms 1784 KB Output is correct
26 Incorrect 8 ms 1784 KB Output isn't correct
27 Halted 0 ms 0 KB -