Submission #5314043
Source Code Expand
#include <bits/stdc++.h> using namespace std; using int64 = long long; const int mod = 1e9 + 7; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename T > struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template< typename T > using Edges = vector< edge< T > >; template< typename T > using WeightedGraph = vector< Edges< T > >; using UnWeightedGraph = vector< vector< int > >; template< typename T > using Matrix = vector< vector< T > >; template< typename T > T maximum_clique(Matrix< T > g) { T INF = numeric_limits< T >::max(); int N = (int) g.size(), M = 0; vector< int > deg(N), v(N); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { assert(g[i][j] == g[j][i]); if(g[i][j] > 0) { ++deg[i]; ++M; } } } int lim = (int) sqrt(M); T ret = 0; for(int i = 0; i < N; i++) { int root = -1; for(int j = 0; j < N; j++) { if(v[j]) continue; if(root == -1 || deg[j] < deg[root]) root = j; } vector< int > rots; for(int j = 0; j < N; j++) { if(j != root && g[root][j] > 0) rots.emplace_back(j); } if(rots.size() >= lim) { vector< int > rest; for(int j = 0; j < N; j++) { if(!v[j]) rest.emplace_back(j); } vector< vector< T > > dp(1 << rest.size(), vector< T >(rest.size(), INF)); for(int j = 1; j < (1 << rest.size()); j++) { int add = __builtin_ctz(j); int base = j - (1 << add); if(base == 0) continue; T sum = 0; for(int k = add + 1; k < rest.size(); k++) { if((j >> k) & 1) { dp[j][add] = min(dp[j][add], g[rest[k]][rest[add]]); dp[j][k] = min(dp[base][k], g[rest[k]][rest[add]]); sum += dp[j][k]; } } ret = max(ret, sum + dp[j][add]); } break; } vector< vector< T > > dp(1 << rots.size(), vector< T >(rots.size() + 1, INF)); for(int j = 1; j < (1 << rots.size()); j++) { int add = __builtin_ctz(j); int base = j - (1 << add); T sum = 0; dp[j][add] = g[rots[add]][root]; dp[j][rots.size()] = min(dp[base][rots.size()], dp[j][add]); for(int k = add + 1; k < rots.size(); k++) { if((j >> k) & 1) { dp[j][add] = min(dp[j][add], g[rots[k]][rots[add]]); dp[j][k] = min(dp[base][k], g[rots[k]][rots[add]]); sum += dp[j][k]; } } ret = max(ret, sum + dp[j][add] + dp[j][rots.size()]); } v[root] = true; for(int j = 0; j < N; j++) { if(g[j][root] > 0) { --deg[j]; g[root][j] = g[j][root] = 0; } } } return ret; } int main() { int N, M; cin >> N >> M; Matrix< int > g(N, vector< int >(N)); for(int i = 0; i < M; i++) { int x, y; cin >> x >> y; --x, --y; g[x][y] = 1; g[y][x] = 1; } cout << max(1, maximum_clique(g)) << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 派閥 |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 4836 Byte |
Status | AC |
Exec Time | 2 ms |
Memory | 640 KB |
Judge Result
Set Name | all | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
all | 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt, test_66.txt, test_67.txt, test_68.txt, test_69.txt, test_70.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 1 ms | 256 KB |
00_sample_02.txt | AC | 1 ms | 256 KB |
00_sample_03.txt | AC | 1 ms | 256 KB |
00_sample_04.txt | AC | 2 ms | 640 KB |
test_01.txt | AC | 1 ms | 256 KB |
test_02.txt | AC | 1 ms | 256 KB |
test_03.txt | AC | 1 ms | 256 KB |
test_04.txt | AC | 1 ms | 256 KB |
test_05.txt | AC | 1 ms | 256 KB |
test_06.txt | AC | 1 ms | 256 KB |
test_07.txt | AC | 1 ms | 256 KB |
test_08.txt | AC | 1 ms | 256 KB |
test_09.txt | AC | 1 ms | 256 KB |
test_10.txt | AC | 1 ms | 256 KB |
test_11.txt | AC | 1 ms | 256 KB |
test_12.txt | AC | 1 ms | 256 KB |
test_13.txt | AC | 1 ms | 256 KB |
test_14.txt | AC | 1 ms | 256 KB |
test_15.txt | AC | 1 ms | 256 KB |
test_16.txt | AC | 1 ms | 256 KB |
test_17.txt | AC | 1 ms | 384 KB |
test_18.txt | AC | 1 ms | 256 KB |
test_19.txt | AC | 1 ms | 256 KB |
test_20.txt | AC | 2 ms | 384 KB |
test_21.txt | AC | 1 ms | 256 KB |
test_22.txt | AC | 1 ms | 384 KB |
test_23.txt | AC | 1 ms | 384 KB |
test_24.txt | AC | 2 ms | 640 KB |
test_25.txt | AC | 1 ms | 256 KB |
test_26.txt | AC | 1 ms | 256 KB |
test_27.txt | AC | 1 ms | 256 KB |
test_28.txt | AC | 1 ms | 256 KB |
test_29.txt | AC | 1 ms | 256 KB |
test_30.txt | AC | 1 ms | 256 KB |
test_31.txt | AC | 1 ms | 256 KB |
test_32.txt | AC | 1 ms | 256 KB |
test_33.txt | AC | 1 ms | 256 KB |
test_34.txt | AC | 1 ms | 384 KB |
test_35.txt | AC | 1 ms | 384 KB |
test_36.txt | AC | 2 ms | 640 KB |
test_37.txt | AC | 1 ms | 256 KB |
test_38.txt | AC | 2 ms | 384 KB |
test_39.txt | AC | 1 ms | 256 KB |
test_40.txt | AC | 1 ms | 256 KB |
test_41.txt | AC | 1 ms | 384 KB |
test_42.txt | AC | 2 ms | 640 KB |
test_43.txt | AC | 1 ms | 256 KB |
test_44.txt | AC | 1 ms | 256 KB |
test_45.txt | AC | 1 ms | 256 KB |
test_46.txt | AC | 1 ms | 256 KB |
test_47.txt | AC | 1 ms | 384 KB |
test_48.txt | AC | 2 ms | 640 KB |
test_49.txt | AC | 1 ms | 256 KB |
test_50.txt | AC | 1 ms | 256 KB |
test_51.txt | AC | 1 ms | 256 KB |
test_52.txt | AC | 1 ms | 256 KB |
test_53.txt | AC | 1 ms | 256 KB |
test_54.txt | AC | 1 ms | 256 KB |
test_55.txt | AC | 1 ms | 256 KB |
test_56.txt | AC | 1 ms | 256 KB |
test_57.txt | AC | 1 ms | 384 KB |
test_58.txt | AC | 1 ms | 256 KB |
test_59.txt | AC | 1 ms | 384 KB |
test_60.txt | AC | 2 ms | 640 KB |
test_61.txt | AC | 2 ms | 640 KB |
test_62.txt | AC | 1 ms | 256 KB |
test_63.txt | AC | 1 ms | 256 KB |
test_64.txt | AC | 1 ms | 256 KB |
test_65.txt | AC | 1 ms | 256 KB |
test_66.txt | AC | 1 ms | 256 KB |
test_67.txt | AC | 1 ms | 256 KB |
test_68.txt | AC | 1 ms | 256 KB |
test_69.txt | AC | 1 ms | 256 KB |
test_70.txt | AC | 1 ms | 256 KB |