oj.uz

Submission #153947

# Submission time Handle Problem Language Result Execution time Memory
153947 2019-09-17T14:44:02 Z Swan Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 17 ms 1784 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("input.txt","r",stdin)
#define OUTP freopen("solve1.txt","w",stdout)
using namespace std;

typedef long long ll;

vector<vector<int>> v;

int ans = 0;
int n,k;

const int maxn = 1e5;
bitset<12> way[12];
int num[maxn];
map<pair<int,int>,bool> is_good;

bool check(int mask,int cnt){
    int res = (1<<22)-1;
    for(int i(0); i < cnt+1;i++){
        if(mask&(1<<i)){
            int to = way[i].to_ullong();
            res&=to;
        }
    }
    for(int i(0); i < cnt+1;i++){
        if(mask&(1<<i)){
            int bit = mask&(1<<i);
            if(!bit)return 0;
        }
    }
    return 1;
}

void solve(int u){
    int pnt = 0;
    vector<int> qwe;
    qwe.push_back(u);
    for(int i(0); i < v[u].size();i++){
        way[pnt][pnt] = 1;
        num[v[u][i]] = pnt++;
        qwe.push_back(v[u][i]);
    }
    num[u] = pnt;
    way[pnt][pnt] = 1;
    for(int i(0); i < qwe.size();i++){
        for(int j(0); j < qwe.size();j++){
            bool f = is_good[{qwe[i],qwe[j]}];
            if(!f)continue;
            way[num[qwe[i]]][num[qwe[j]]] = 1;
        }
    }
    /*if(!u){
        cout << pnt << endl;
        for(int i(0); i < 4;i++){
            for(int j(0); j < 4;j++){
                cout << way[i][j] << ' ';
            }
            cout << endl;
        }
    }*/
    int lim = (1<<(v[u].size()+1));
    for(int i(0); i < lim;i++){
        bool f = check(i,v[u].size()+1);
        if(!f)continue;
        int x = i;
        int now = 0;
        while(x){
            now+=(x%2);
            x/=2;
        }
        //if(u == 0)cout << i << endl;
        ans = max(now,ans);
    }
}

main()
{
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    v.resize(n+2);
    for(int i(0); i < n;i++){
        int sz; cin >> sz;
        for(int j(0); j < sz;j++){
            int x; cin >> x;
            v[i].push_back(x);
            is_good[{i,x}] = 1;
        }
    }
    for(int i(0); i < n;i++){
        if(v[i].size() < k)solve(i);
    }
    cout << ans;
    return 0;
}
/*
*/

Compilation message

politicaldevelopment.cpp: In function 'void solve(int)':
politicaldevelopment.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v[u].size();i++){
                   ~~^~~~~~~~~~~~~
politicaldevelopment.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < qwe.size();i++){
                   ~~^~~~~~~~~~~~
politicaldevelopment.cpp:48:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j(0); j < qwe.size();j++){
                       ~~^~~~~~~~~~~~
politicaldevelopment.cpp: At global scope:
politicaldevelopment.cpp:78:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v[i].size() < k)solve(i);
            ~~~~~~~~~~~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 9 ms 1656 KB Output is correct
4 Correct 10 ms 1660 KB Output is correct
5 Correct 10 ms 1784 KB Output is correct
6 Correct 10 ms 1656 KB Output is correct
7 Correct 11 ms 1656 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 4 ms 760 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 9 ms 1656 KB Output is correct
4 Correct 10 ms 1660 KB Output is correct
5 Correct 10 ms 1784 KB Output is correct
6 Correct 10 ms 1656 KB Output is correct
7 Correct 11 ms 1656 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 10 ms 1656 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 9 ms 1656 KB Output is correct
4 Correct 10 ms 1660 KB Output is correct
5 Correct 10 ms 1784 KB Output is correct
6 Correct 10 ms 1656 KB Output is correct
7 Correct 11 ms 1656 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 10 ms 1656 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 9 ms 1656 KB Output is correct
4 Correct 10 ms 1660 KB Output is correct
5 Correct 10 ms 1784 KB Output is correct
6 Correct 10 ms 1656 KB Output is correct
7 Correct 11 ms 1656 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 4 ms 760 KB Output is correct
11 Correct 10 ms 1656 KB Output is correct
12 Correct 10 ms 1656 KB Output is correct
13 Incorrect 2 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -