oj.uz

Submission #1115871

# Submission time Handle Problem Language Result Execution time Memory
1115871 2024-11-21T02:59:48 Z binminh01 Political Development (BOI17_politicaldevelopment) C++17
54 / 100
 3000 ms 321348 KB 
#include<bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define double long double
#define gcd __gcd
#define lcm(a, b) ((a)/gcd(a, b)*(b))
#define sqrt sqrtl
#define log2 log2l
#define log10 log10l
#define floor floorl
#define to_string str
#define yes cout << "YES"
#define no cout << "NO"
#define trav(i, a) for (auto &i: (a))
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(a) (int)a.size()
#define Max(a) *max_element(all(a))
#define Min(a) *min_element(all(a))
#define Find(a, n) (find(all(a), n) - a.begin())
#define Count(a, n) count(all(a), n)
#define Upper(a, n) (upper_bound(all(a), n) - a.begin())
#define Lower(a, n) (lower_bound(all(a), n) - a.begin())
#define next_perm(a) next_permutation(all(a))
#define prev_perm(a) prev_permutation(all(a))
#define sorted(a) is_sorted(all(a))
#define sum(a) accumulate(all(a), 0)
#define sumll(a) accumulate(all(a), 0ll)
#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))
#define Unique(a) Sort(a), (a).resize(unique(all(a)) - a.begin())
#define pb push_back
#define eb emplace_back
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __buitlin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define open(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define fileopen(s) open((string(s) + ".inp").c_str()), write((string(s) + ".out").c_str());
#define For(i, a, b) for (auto i = (a); i < (b); ++i)
#define Fore(i, a, b) for (auto i = (a); i >= (b); --i)
#define FOR(i, a, b) for (auto i = (a); i <= (b); ++i)
#define ret(s) return void(cout << s);

constexpr int mod = 1e9 + 7, mod2 = 998244353;
constexpr double eps = 1e-9;
const double PI = acos(-1);
constexpr ull npos = string::npos;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using cd = complex<double>;
mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 mt64(chrono::system_clock::now().time_since_epoch().count());
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vdo;
typedef vector<vdo> vvdo;
typedef vector<string> vs;
typedef vector<pii> vpair;
typedef vector<vpair> vvpair;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<cd> vcd;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi, greater<int>> pqg;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vll, greater<ll>> pqgll;

ll add(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;a+=b;return a >= m ? a - m: a;}
ll sub(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;a-=b;return a < 0 ? a + m: a;}
ll mul(ll a, ll b, int m) {if (a >= m) a%=m;if (b >= m) b%=m;return a*b % m;}
ll bin_mul(ll a, ll b, ll m) {if (a >= m) a%=m;if (b >= m) b%=m;ll x = 0;while (b) {if (b & 1) x = (x + a) % m;a = (a + a) % m;b>>=1;}return x;}
ll bin_pow(ll a, ll b, ll m) {ll x = 1;if (a >= m) a%=m; while (b) {if (b & 1) x = bin_mul(x, a, m);a = bin_mul(a, a, m);b>>=1;}return x;}
ll power(ll a, ll b, int m) {ll x = 1;if (a >= m) a%=m; while (b) {if (b & 1) x = x*a % m;a = a*a % m;b>>=1;}return x;}
ll power(ll a, ll b) {ll x = 1;while (b) {if (b & 1) x = x*a;a = a*a;b>>=1;}return x;}
ll ceil(ll a, ll b) {return (a + b - 1)/b;}
ll to_int(const string &s) {ll x = 0; for (int i = (s[0] == '-'); i < sz(s); ++i) x = x*10 + s[i] - '0';return x*(s[0] == '-' ? -1: 1);}
bool is_prime(ll n) {if (n < 2) return 0;if (n < 4) return 1;if (n % 2 == 0 || n % 3 == 0) return 0;for (ll i = 5; i*i <= n; i+=6) {if(n % i == 0 || n % (i + 2) == 0) return 0;}return 1;}
bool is_square(ll n) {ll k = sqrt(n); return k*k == n;}
ll factorial(int n) {ll x = 1;for (int i = 2; i <= n; ++i) x*=i;return x;}
ll factorial(int n, int m) {ll x = 1;for (ll i = 2; i <= n; ++i) x = x*i % m;return x;}
bool is_power(ll n, ll k) {while (n % k == 0) n/=k;return n == 1ll;}
string str(ll n) {if (n == 0) return "0"; string s = ""; bool c = 0; if (n < 0) c = 1, n = -n; while (n) {s+=n % 10 + '0'; n/=10;} if (c) s+='-'; Reverse(s); return s;}
string repeat(const string &s, int n) {if (n < 0) return ""; string x = ""; while (n--) x+=s; return x;}
string bin(ll n) {string s = ""; while (n) {s+=(n & 1) + '0'; n>>=1;} Reverse(s); return s;}
void sieve(vector<bool> &a) {int n = a.size(); a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(bool a[], int n) {a[0] = a[1] = 0; for (int i = 4; i < n; i+=2) a[i] = 0; for (int i = 3; i*i < n; i+=2) {if (a[i]) {for (int j = i*i; j < n; j+=(i << 1)) a[j] = 0;}}}
void sieve(vector<int> &a) {int n = a.size(); for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
void sieve(int a[], int n) {for (int i = 2; i < n; i+=2) a[i] = 2; for (int i = 3; i*i < n; i+=2) {if (!a[i]) {for (int j = i; j < n; j+=(i << 1)) a[j] = i;}} for (int i = 3; i < n; i+=2) {if (!a[i]) a[i] = i;}}
vector<pii> factorize(int n) {vector<pii> a; for (int i = 2; i*i <= n; ++i) {if (n % i == 0) {int k = 0; while (n % i == 0) ++k, n/=i; a.emplace_back(i, k);}} if (n > 1) a.emplace_back(n, 1); return a;}
int rand(int l, int r) {return uniform_int_distribution<int>(l, r)(mt);}
ll rand(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(mt64);}
int Log2(int n) {return 31 - __builtin_clz(n);}
ll Log2(ll n) {return 63 - __builtin_clzll(n);}
template<class T> void compress(vector<T> &a) {vector<T> b; for (T &i: a) b.push_back(i); sort(all(b)); b.resize(unique(all(b)) - b.begin()); for (T &i: a) i = lower_bound(all(b), i) - b.begin() + 1;}
template<class A, class B> bool ckmin(A &a, const B &b) {return a > b ? a = b, 1: 0;}
template<class A, class B> bool ckmax(A &a, const B &b) {return a < b ? a = b, 1: 0;}

template<class A, class B> istream& operator>>(istream& in, pair<A, B> &p) {in >> p.first >> p.second; return in;}
template<class A, class B> ostream& operator<<(ostream& out, const pair<A, B> &p) {out << p.first << ' ' << p.second; return out;}
template<class T> istream& operator>>(istream& in, vector<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<T> &a) {for (auto &i: a) out << i << ' '; return out;}
template<class T> istream& operator>>(istream& in, vector<vector<T>> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const vector<vector<T>> &a) {for (auto &i: a) out << i << '\n'; return out;}
template<class T> istream& operator>>(istream& in, deque<T> &a) {for (auto &i: a) in >> i; return in;}
template<class T> ostream& operator<<(ostream& out, const deque<T> &a) {for (auto &i: a) out << i << ' '; return out;}
// istream& operator>>(istream& in, __int128_t &a) {string s; in >> s; a = 0; for (auto &i: s) a = a*10 + (i - '0'); return in;}
// ostream& operator<<(ostream& out, __int128_t a) {string s = ""; if (a < 0) s+='-', a = -a; if (a == 0) s+='0'; while (a > 0) {s+=(int)(a % 10) + '0'; a/=10;} Reverse(s); out << s; return out;}

int n, k, x;
bitset<50000> g[50000];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cout << fixed << setprecision(10);
    cin >> n >> k;
    For(i,0,n){
        int t; cin >> t;
        while (t--) {
            int j; cin >> j;
            if (i < j) g[i][j] = 1;
        }
    }
    vvi a;
    For(i,0,n) a.pb({i});
    FOR(s,2,k){
        vvi b;
        trav(c,a){
            For(u,c.back()+1,n){
                bool o = 1;
                trav(v,c){
                    if (!g[v][u]) {o = 0; break;}
                }
                if (o) b.pb(c), b.back().pb(u);
            }
        }
        a.swap(b);
        if (a.empty()) return cout << s - 1, 0;
    }
    cout << k;
    cerr << "\nProcess returned 0 (0x0)   execution time :  " << 0.001*clock() << " s";
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 32 ms 31824 KB Output is correct
4 Correct 25 ms 11480 KB Output is correct
5 Correct 28 ms 13392 KB Output is correct
6 Correct 27 ms 31824 KB Output is correct
7 Correct 28 ms 31824 KB Output is correct
8 Correct 55 ms 840 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 24 ms 2896 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 32 ms 31824 KB Output is correct
4 Correct 25 ms 11480 KB Output is correct
5 Correct 28 ms 13392 KB Output is correct
6 Correct 27 ms 31824 KB Output is correct
7 Correct 28 ms 31824 KB Output is correct
8 Correct 55 ms 840 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 24 ms 2896 KB Output is correct
11 Correct 26 ms 9296 KB Output is correct
12 Correct 58 ms 11344 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 50 ms 19528 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 46 ms 31824 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 57 ms 31816 KB Output is correct
19 Correct 27 ms 848 KB Output is correct
20 Correct 39 ms 11616 KB Output is correct
21 Correct 35 ms 19536 KB Output is correct
22 Correct 23 ms 2896 KB Output is correct
23 Correct 45 ms 31824 KB Output is correct
24 Correct 52 ms 2892 KB Output is correct
25 Correct 53 ms 31760 KB Output is correct
26 Correct 62 ms 14148 KB Output is correct
27 Correct 45 ms 22344 KB Output is correct
28 Correct 45 ms 24872 KB Output is correct
29 Correct 42 ms 24912 KB Output is correct
30 Correct 51 ms 24524 KB Output is correct
31 Correct 56 ms 31832 KB Output is correct
32 Correct 66 ms 12112 KB Output is correct
33 Correct 66 ms 21852 KB Output is correct
34 Correct 90 ms 19036 KB Output is correct
35 Correct 14 ms 12112 KB Output is correct
36 Correct 18 ms 10064 KB Output is correct
37 Correct 14 ms 15184 KB Output is correct
38 Correct 7 ms 8784 KB Output is correct
39 Correct 8 ms 8956 KB Output is correct
40 Correct 61 ms 23692 KB Output is correct
41 Correct 6 ms 8784 KB Output is correct
42 Correct 64 ms 32140 KB Output is correct
43 Correct 105 ms 27208 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 832 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Execution timed out 3072 ms 321348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 32 ms 31824 KB Output is correct
4 Correct 25 ms 11480 KB Output is correct
5 Correct 28 ms 13392 KB Output is correct
6 Correct 27 ms 31824 KB Output is correct
7 Correct 28 ms 31824 KB Output is correct
8 Correct 55 ms 840 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 24 ms 2896 KB Output is correct
11 Correct 26 ms 9296 KB Output is correct
12 Correct 58 ms 11344 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 50 ms 19528 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 46 ms 31824 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 57 ms 31816 KB Output is correct
19 Correct 27 ms 848 KB Output is correct
20 Correct 39 ms 11616 KB Output is correct
21 Correct 35 ms 19536 KB Output is correct
22 Correct 23 ms 2896 KB Output is correct
23 Correct 45 ms 31824 KB Output is correct
24 Correct 52 ms 2892 KB Output is correct
25 Correct 53 ms 31760 KB Output is correct
26 Correct 62 ms 14148 KB Output is correct
27 Correct 45 ms 22344 KB Output is correct
28 Correct 45 ms 24872 KB Output is correct
29 Correct 42 ms 24912 KB Output is correct
30 Correct 51 ms 24524 KB Output is correct
31 Correct 56 ms 31832 KB Output is correct
32 Correct 66 ms 12112 KB Output is correct
33 Correct 66 ms 21852 KB Output is correct
34 Correct 90 ms 19036 KB Output is correct
35 Correct 14 ms 12112 KB Output is correct
36 Correct 18 ms 10064 KB Output is correct
37 Correct 14 ms 15184 KB Output is correct
38 Correct 7 ms 8784 KB Output is correct
39 Correct 8 ms 8956 KB Output is correct
40 Correct 61 ms 23692 KB Output is correct
41 Correct 6 ms 8784 KB Output is correct
42 Correct 64 ms 32140 KB Output is correct
43 Correct 105 ms 27208 KB Output is correct
44 Correct 660 ms 42140 KB Output is correct
45 Correct 1 ms 504 KB Output is correct
46 Correct 59 ms 32144 KB Output is correct
47 Correct 88 ms 32908 KB Output is correct
48 Correct 65 ms 32140 KB Output is correct
49 Correct 138 ms 33080 KB Output is correct
50 Correct 92 ms 32812 KB Output is correct
51 Correct 173 ms 34056 KB Output is correct
52 Correct 24 ms 3312 KB Output is correct
53 Correct 208 ms 34120 KB Output is correct
54 Correct 224 ms 34212 KB Output is correct
55 Correct 50 ms 31816 KB Output is correct
56 Correct 26 ms 3320 KB Output is correct
57 Correct 29 ms 848 KB Output is correct
58 Correct 211 ms 30024 KB Output is correct
59 Correct 120 ms 32536 KB Output is correct
60 Correct 45 ms 31764 KB Output is correct
61 Correct 108 ms 32524 KB Output is correct
62 Correct 131 ms 32552 KB Output is correct
63 Correct 722 ms 42188 KB Output is correct
64 Correct 454 ms 36708 KB Output is correct
65 Correct 75 ms 32132 KB Output is correct
66 Correct 117 ms 18188 KB Output is correct
67 Correct 269 ms 24480 KB Output is correct
68 Correct 451 ms 36720 KB Output is correct
69 Correct 68 ms 16672 KB Output is correct
70 Correct 128 ms 19676 KB Output is correct
71 Correct 266 ms 23380 KB Output is correct
72 Correct 204 ms 20872 KB Output is correct
73 Correct 85 ms 23368 KB Output is correct
74 Correct 114 ms 32888 KB Output is correct
75 Correct 209 ms 20680 KB Output is correct
76 Correct 64 ms 27112 KB Output is correct
77 Correct 116 ms 28408 KB Output is correct
78 Correct 41 ms 31816 KB Output is correct
79 Correct 33 ms 17804 KB Output is correct
80 Correct 84 ms 18820 KB Output is correct
81 Correct 116 ms 33004 KB Output is correct
82 Correct 5 ms 8784 KB Output is correct
83 Correct 33 ms 17804 KB Output is correct
84 Correct 108 ms 20956 KB Output is correct
85 Correct 12 ms 3796 KB Output is correct
86 Correct 118 ms 31228 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 32 ms 31824 KB Output is correct
4 Correct 25 ms 11480 KB Output is correct
5 Correct 28 ms 13392 KB Output is correct
6 Correct 27 ms 31824 KB Output is correct
7 Correct 28 ms 31824 KB Output is correct
8 Correct 55 ms 840 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 24 ms 2896 KB Output is correct
11 Correct 26 ms 9296 KB Output is correct
12 Correct 58 ms 11344 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 50 ms 19528 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 46 ms 31824 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 57 ms 31816 KB Output is correct
19 Correct 27 ms 848 KB Output is correct
20 Correct 39 ms 11616 KB Output is correct
21 Correct 35 ms 19536 KB Output is correct
22 Correct 23 ms 2896 KB Output is correct
23 Correct 45 ms 31824 KB Output is correct
24 Correct 52 ms 2892 KB Output is correct
25 Correct 53 ms 31760 KB Output is correct
26 Correct 62 ms 14148 KB Output is correct
27 Correct 45 ms 22344 KB Output is correct
28 Correct 45 ms 24872 KB Output is correct
29 Correct 42 ms 24912 KB Output is correct
30 Correct 51 ms 24524 KB Output is correct
31 Correct 56 ms 31832 KB Output is correct
32 Correct 66 ms 12112 KB Output is correct
33 Correct 66 ms 21852 KB Output is correct
34 Correct 90 ms 19036 KB Output is correct
35 Correct 14 ms 12112 KB Output is correct
36 Correct 18 ms 10064 KB Output is correct
37 Correct 14 ms 15184 KB Output is correct
38 Correct 7 ms 8784 KB Output is correct
39 Correct 8 ms 8956 KB Output is correct
40 Correct 61 ms 23692 KB Output is correct
41 Correct 6 ms 8784 KB Output is correct
42 Correct 64 ms 32140 KB Output is correct
43 Correct 105 ms 27208 KB Output is correct
44 Correct 1 ms 336 KB Output is correct
45 Execution timed out 3091 ms 232048 KB Time limit exceeded
46 Halted 0 ms 0 KB -