oj.uz

Submission #153982

# Submission time Handle Problem Language Result Execution time Memory
153982 2019-09-17T16:05:40 Z Swan Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 3000 ms 142304 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 = res&(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 < 12;i++)way[i] = 0;
    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]}] && is_good[{qwe[j],qwe[i]}]);
            if(!f){
                continue;
            }
            way[num[qwe[i]]][num[qwe[j]]] = 1;
        }
    }
    int lim = (1<<(v[u].size()+1));
    for(int i(0); i < lim;i++){
        bool f = check(i,v[u].size());
        if(!f)continue;
        int x = i;
        int now = 0;
        while(x){
            now+=(x%2);
            x/=2;
        }
        //if(u == 0)cout << i << ' ' << now << 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;
}
/*
3 10
0
0
0
*/

Compilation message

politicaldevelopment.cpp: In function 'void solve(int)':
politicaldevelopment.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < v[u].size();i++){
                   ~~^~~~~~~~~~~~~
politicaldevelopment.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i(0); i < qwe.size();i++){
                   ~~^~~~~~~~~~~~
politicaldevelopment.cpp:49: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:72:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:86: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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 11 ms 1656 KB Output is correct
6 Correct 12 ms 1656 KB Output is correct
7 Correct 12 ms 1808 KB Output is correct
8 Correct 4 ms 764 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 11 ms 1656 KB Output is correct
6 Correct 12 ms 1656 KB Output is correct
7 Correct 12 ms 1808 KB Output is correct
8 Correct 4 ms 764 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 11 ms 1656 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 12 ms 1708 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 1656 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 12 ms 1656 KB Output is correct
19 Correct 4 ms 760 KB Output is correct
20 Correct 10 ms 1272 KB Output is correct
21 Correct 10 ms 1256 KB Output is correct
22 Correct 4 ms 760 KB Output is correct
23 Incorrect 15 ms 2040 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Execution timed out 3063 ms 142304 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 11 ms 1656 KB Output is correct
6 Correct 12 ms 1656 KB Output is correct
7 Correct 12 ms 1808 KB Output is correct
8 Correct 4 ms 764 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 11 ms 1656 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 12 ms 1708 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 1656 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 12 ms 1656 KB Output is correct
19 Correct 4 ms 760 KB Output is correct
20 Correct 10 ms 1272 KB Output is correct
21 Correct 10 ms 1256 KB Output is correct
22 Correct 4 ms 760 KB Output is correct
23 Incorrect 15 ms 2040 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 10 ms 1528 KB Output is correct
4 Correct 11 ms 1656 KB Output is correct
5 Correct 11 ms 1656 KB Output is correct
6 Correct 12 ms 1656 KB Output is correct
7 Correct 12 ms 1808 KB Output is correct
8 Correct 4 ms 764 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 11 ms 1656 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 12 ms 1708 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 13 ms 1656 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 12 ms 1656 KB Output is correct
19 Correct 4 ms 760 KB Output is correct
20 Correct 10 ms 1272 KB Output is correct
21 Correct 10 ms 1256 KB Output is correct
22 Correct 4 ms 760 KB Output is correct
23 Incorrect 15 ms 2040 KB Output isn't correct
24 Halted 0 ms 0 KB -