oj.uz

Submission #367467

# Submission time Handle Problem Language Result Execution time Memory
367467 2021-02-17T12:52:35 Z ACmachine Political Development (BOI17_politicaldevelopment) C++17
100 / 100
 416 ms 32236 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int> deg(n, 0);
    vector<vector<int>> g(n); 
    vector<unordered_set<int>> mat(n);
    vector<bool> alive(n, true);
    REP(i, n){
        cin >> deg[i];
        REP(j, deg[i]){
            int x; cin >> x;
            g[i].pb(x); 
            mat[i].insert(x);
        }
    }
    int ans = 0;
    set<pair<int, int>> q;
    REP(i, n) q.insert(mp(deg[i], i));
    vector<int> alive_adj;
    while(!q.empty()){
        alive_adj.clear();
        pair<int, int> v = *q.begin();
        alive[v.ss] = false;
        q.erase(q.begin());
        for(int x : g[v.ss]){
            if(alive[x])
                alive_adj.pb(x);
        }
        REP(sub, (1 << (int)alive_adj.size())){
            bool is_clique = true;
            REP(j, alive_adj.size()){
                if(!(sub&(1 << j))) continue;
                if(!is_clique) break;
                REP(g, alive_adj.size()){
                    if(!(sub&(1 << g))) continue;
                    if(j == g) continue;
                    if(mat[alive_adj[j]].find(alive_adj[g]) == mat[alive_adj[j]].end()){
                        is_clique = false;
                        break;
                    }
                }
            }
            if(is_clique)
                ans = max(ans, __builtin_popcount(sub) + 1);
        }
        for(int x : g[v.ss]){
            if(alive[x]){
                q.erase(mp(deg[x], x));
                deg[x]--;
                q.insert(mp(deg[x], x));
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
politicaldevelopment.cpp:28:18: note: in expansion of macro 'FOR'
   28 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
politicaldevelopment.cpp:117:13: note: in expansion of macro 'REP'
  117 |             REP(j, alive_adj.size()){
      |             ^~~
politicaldevelopment.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
politicaldevelopment.cpp:28:18: note: in expansion of macro 'FOR'
   28 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
politicaldevelopment.cpp:120:17: note: in expansion of macro 'REP'
  120 |                 REP(g, alive_adj.size()){
      |                 ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 7 ms 1644 KB Output is correct
4 Correct 6 ms 1772 KB Output is correct
5 Correct 6 ms 1772 KB Output is correct
6 Correct 7 ms 1772 KB Output is correct
7 Correct 7 ms 1772 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 7 ms 1644 KB Output is correct
4 Correct 6 ms 1772 KB Output is correct
5 Correct 6 ms 1772 KB Output is correct
6 Correct 7 ms 1772 KB Output is correct
7 Correct 7 ms 1772 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 6 ms 1772 KB Output is correct
12 Correct 6 ms 1772 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 6 ms 1772 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 9 ms 1772 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 7 ms 1772 KB Output is correct
19 Correct 2 ms 1004 KB Output is correct
20 Correct 5 ms 1516 KB Output is correct
21 Correct 5 ms 1516 KB Output is correct
22 Correct 2 ms 1004 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 2 ms 1004 KB Output is correct
25 Correct 9 ms 1772 KB Output is correct
26 Correct 8 ms 1772 KB Output is correct
27 Correct 7 ms 1644 KB Output is correct
28 Correct 8 ms 1772 KB Output is correct
29 Correct 7 ms 1664 KB Output is correct
30 Correct 8 ms 1900 KB Output is correct
31 Correct 9 ms 1772 KB Output is correct
32 Correct 8 ms 1900 KB Output is correct
33 Correct 9 ms 1772 KB Output is correct
34 Correct 9 ms 1772 KB Output is correct
35 Correct 5 ms 1132 KB Output is correct
36 Correct 4 ms 1132 KB Output is correct
37 Correct 4 ms 1132 KB Output is correct
38 Correct 3 ms 748 KB Output is correct
39 Correct 3 ms 748 KB Output is correct
40 Correct 12 ms 2156 KB Output is correct
41 Correct 3 ms 748 KB Output is correct
42 Correct 13 ms 2156 KB Output is correct
43 Correct 12 ms 2156 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1004 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 405 ms 32236 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 406 ms 32236 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 413 ms 32236 KB Output is correct
16 Correct 405 ms 32108 KB Output is correct
17 Correct 416 ms 32108 KB Output is correct
18 Correct 410 ms 32108 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 7 ms 1644 KB Output is correct
4 Correct 6 ms 1772 KB Output is correct
5 Correct 6 ms 1772 KB Output is correct
6 Correct 7 ms 1772 KB Output is correct
7 Correct 7 ms 1772 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 6 ms 1772 KB Output is correct
12 Correct 6 ms 1772 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 6 ms 1772 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 9 ms 1772 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 7 ms 1772 KB Output is correct
19 Correct 2 ms 1004 KB Output is correct
20 Correct 5 ms 1516 KB Output is correct
21 Correct 5 ms 1516 KB Output is correct
22 Correct 2 ms 1004 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 2 ms 1004 KB Output is correct
25 Correct 9 ms 1772 KB Output is correct
26 Correct 8 ms 1772 KB Output is correct
27 Correct 7 ms 1644 KB Output is correct
28 Correct 8 ms 1772 KB Output is correct
29 Correct 7 ms 1664 KB Output is correct
30 Correct 8 ms 1900 KB Output is correct
31 Correct 9 ms 1772 KB Output is correct
32 Correct 8 ms 1900 KB Output is correct
33 Correct 9 ms 1772 KB Output is correct
34 Correct 9 ms 1772 KB Output is correct
35 Correct 5 ms 1132 KB Output is correct
36 Correct 4 ms 1132 KB Output is correct
37 Correct 4 ms 1132 KB Output is correct
38 Correct 3 ms 748 KB Output is correct
39 Correct 3 ms 748 KB Output is correct
40 Correct 12 ms 2156 KB Output is correct
41 Correct 3 ms 748 KB Output is correct
42 Correct 13 ms 2156 KB Output is correct
43 Correct 12 ms 2156 KB Output is correct
44 Correct 108 ms 3180 KB Output is correct
45 Correct 1 ms 364 KB Output is correct
46 Correct 13 ms 2156 KB Output is correct
47 Correct 25 ms 3180 KB Output is correct
48 Correct 13 ms 2156 KB Output is correct
49 Correct 26 ms 3308 KB Output is correct
50 Correct 25 ms 3180 KB Output is correct
51 Correct 80 ms 5356 KB Output is correct
52 Correct 6 ms 1772 KB Output is correct
53 Correct 67 ms 5868 KB Output is correct
54 Correct 120 ms 5868 KB Output is correct
55 Correct 6 ms 1772 KB Output is correct
56 Correct 6 ms 1772 KB Output is correct
57 Correct 2 ms 1004 KB Output is correct
58 Correct 66 ms 5868 KB Output is correct
59 Correct 12 ms 2156 KB Output is correct
60 Correct 7 ms 1792 KB Output is correct
61 Correct 15 ms 2156 KB Output is correct
62 Correct 12 ms 2156 KB Output is correct
63 Correct 103 ms 3180 KB Output is correct
64 Correct 53 ms 2924 KB Output is correct
65 Correct 11 ms 2028 KB Output is correct
66 Correct 12 ms 2156 KB Output is correct
67 Correct 63 ms 3692 KB Output is correct
68 Correct 50 ms 2924 KB Output is correct
69 Correct 12 ms 2028 KB Output is correct
70 Correct 24 ms 2924 KB Output is correct
71 Correct 54 ms 3564 KB Output is correct
72 Correct 49 ms 3564 KB Output is correct
73 Correct 6 ms 1644 KB Output is correct
74 Correct 25 ms 3052 KB Output is correct
75 Correct 40 ms 3564 KB Output is correct
76 Correct 15 ms 2540 KB Output is correct
77 Correct 49 ms 4076 KB Output is correct
78 Correct 8 ms 1644 KB Output is correct
79 Correct 21 ms 2156 KB Output is correct
80 Correct 15 ms 2540 KB Output is correct
81 Correct 51 ms 4076 KB Output is correct
82 Correct 3 ms 748 KB Output is correct
83 Correct 21 ms 2284 KB Output is correct
84 Correct 30 ms 3436 KB Output is correct
85 Correct 3 ms 748 KB Output is correct
86 Correct 30 ms 3436 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 7 ms 1644 KB Output is correct
4 Correct 6 ms 1772 KB Output is correct
5 Correct 6 ms 1772 KB Output is correct
6 Correct 7 ms 1772 KB Output is correct
7 Correct 7 ms 1772 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 6 ms 1772 KB Output is correct
12 Correct 6 ms 1772 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 6 ms 1772 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 9 ms 1772 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 7 ms 1772 KB Output is correct
19 Correct 2 ms 1004 KB Output is correct
20 Correct 5 ms 1516 KB Output is correct
21 Correct 5 ms 1516 KB Output is correct
22 Correct 2 ms 1004 KB Output is correct
23 Correct 9 ms 1772 KB Output is correct
24 Correct 2 ms 1004 KB Output is correct
25 Correct 9 ms 1772 KB Output is correct
26 Correct 8 ms 1772 KB Output is correct
27 Correct 7 ms 1644 KB Output is correct
28 Correct 8 ms 1772 KB Output is correct
29 Correct 7 ms 1664 KB Output is correct
30 Correct 8 ms 1900 KB Output is correct
31 Correct 9 ms 1772 KB Output is correct
32 Correct 8 ms 1900 KB Output is correct
33 Correct 9 ms 1772 KB Output is correct
34 Correct 9 ms 1772 KB Output is correct
35 Correct 5 ms 1132 KB Output is correct
36 Correct 4 ms 1132 KB Output is correct
37 Correct 4 ms 1132 KB Output is correct
38 Correct 3 ms 748 KB Output is correct
39 Correct 3 ms 748 KB Output is correct
40 Correct 12 ms 2156 KB Output is correct
41 Correct 3 ms 748 KB Output is correct
42 Correct 13 ms 2156 KB Output is correct
43 Correct 12 ms 2156 KB Output is correct
44 Correct 1 ms 364 KB Output is correct
45 Correct 240 ms 24172 KB Output is correct
46 Correct 104 ms 16364 KB Output is correct
47 Correct 252 ms 24044 KB Output is correct
48 Correct 252 ms 24300 KB Output is correct
49 Correct 62 ms 14452 KB Output is correct
50 Correct 182 ms 28404 KB Output is correct
51 Correct 251 ms 24172 KB Output is correct
52 Correct 61 ms 14700 KB Output is correct
53 Correct 62 ms 14452 KB Output is correct
54 Correct 18 ms 6892 KB Output is correct
55 Correct 180 ms 28424 KB Output is correct
56 Correct 49 ms 11884 KB Output is correct
57 Correct 62 ms 14700 KB Output is correct
58 Correct 102 ms 16364 KB Output is correct
59 Correct 49 ms 11884 KB Output is correct
60 Correct 48 ms 11884 KB Output is correct
61 Correct 108 ms 16364 KB Output is correct
62 Correct 72 ms 13676 KB Output is correct
63 Correct 147 ms 17516 KB Output is correct
64 Correct 50 ms 11884 KB Output is correct
65 Correct 199 ms 20252 KB Output is correct
66 Correct 73 ms 13676 KB Output is correct
67 Correct 141 ms 17644 KB Output is correct
68 Correct 173 ms 19564 KB Output is correct
69 Correct 187 ms 20076 KB Output is correct
70 Correct 116 ms 13676 KB Output is correct
71 Correct 174 ms 19436 KB Output is correct
72 Correct 118 ms 17516 KB Output is correct
73 Correct 208 ms 21484 KB Output is correct
74 Correct 76 ms 13804 KB Output is correct
75 Correct 76 ms 9324 KB Output is correct
76 Correct 115 ms 17388 KB Output is correct
77 Correct 203 ms 21740 KB Output is correct
78 Correct 101 ms 10988 KB Output is correct
79 Correct 79 ms 9416 KB Output is correct
80 Correct 26 ms 4972 KB Output is correct
81 Correct 104 ms 10988 KB Output is correct
82 Correct 155 ms 18156 KB Output is correct
83 Correct 27 ms 4972 KB Output is correct
84 Correct 159 ms 18184 KB Output is correct