이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#ifndef LOCAL
#define FAST_IO
#endif
// ============
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
template <typename T>
using Vec = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
istream &operator>>(istream &is, i128 &x) {
i64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, i128 x) {
os << (i64)x;
return os;
}
istream &operator>>(istream &is, u128 &x) {
u64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, u128 x) {
os << (u64)x;
return os;
}
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
SetUpIO() {
#ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cout << fixed << setprecision(15);
}
} set_up_io;
// ============
#ifdef DEBUGF
#else
#define DBG(x) (void)0
#endif
int main() {
i32 n, k;
cin >> n >> k;
Vec<Vec<i32>> edge(n, Vec<i32>(n, 0));
Vec<i32> deg(n);
REP(i, n) {
cin >> deg[i];
REP(j, deg[i]) {
i32 v;
cin >> v;
edge[i][v] = 1;
}
}
priority_queue<pair<i32, i32>, Vec<pair<i32, i32>>, greater<>> pq;
REP(i, n) {
pq.emplace(deg[i], i);
}
Vec<i32> alive(n, 1);
i32 ans = 0;
while (!pq.empty()) {
auto [_, v] = pq.top();
pq.pop();
if (!alive[v]) {
continue;
}
Vec<i32> lis;
REP(u, n) {
if (alive[u] && edge[v][u]) {
lis.push_back(u);
}
}
i32 d = (i32)lis.size();
REP(st, 1 << d) {
bool ok = true;
REP(i, d) {
if (!(st & (1 << i))) {
continue;
}
REP(j, i) {
if (!(st & (1 << j))) {
continue;
}
if (!edge[lis[i]][lis[j]]) {
ok = false;
}
}
}
if (ok) {
chmax(ans, __builtin_popcount(st) + 1);
}
}
alive[v] = 0;
REP(u, n) {
if (alive[u]) {
pq.emplace(--deg[u], u);
}
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |