Submission #5312898
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 > vector< int > maximum_independent_set(const Matrix< T > &g, int trial = 10000000) { int N = (int) g.size(); vector< uint64_t > bit(N); assert(N <= 64); for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(i != j) { assert(g[i][j] == g[j][i]); if(g[i][j]) bit[i] |= uint64_t(1) << j; } } } vector< int > ord(N); iota(begin(ord), end(ord), 0); mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); int ret = 0; uint64_t ver; for(int i = 0; i < trial; i++) { shuffle(begin(ord), end(ord), mt); uint64_t used = 0; int add = 0; for(int j : ord) { if(used & bit[j]) continue; used |= uint64_t(1) << j; ++add; } if(ret < add) { ret = add; ver = used; } } vector< int > ans; for(int i = 0; i < N; i++) { if((ver >> i) & 1) ans.emplace_back(i); } return ans; } int main() { int N, M; cin >> N >> M; Matrix< int > g(N, vector< int >(N, true)); for(int i = 0; i < M; i++) { int x, y; cin >> x >> y; --x, --y; g[x][y] = g[y][x] = false; } cout << maximum_independent_set(g).size() << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 派閥 |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3546 Byte |
Status | TLE |
Exec Time | 2103 ms |
Memory | 256 KB |
Judge Result
Set Name | all | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 1201 ms | 256 KB |
00_sample_02.txt | AC | 1206 ms | 256 KB |
00_sample_03.txt | AC | 1854 ms | 256 KB |
00_sample_04.txt | TLE | 2103 ms | 256 KB |
test_01.txt | AC | 24 ms | 256 KB |
test_02.txt | AC | 296 ms | 256 KB |
test_03.txt | AC | 662 ms | 256 KB |
test_04.txt | AC | 962 ms | 256 KB |
test_05.txt | AC | 1166 ms | 256 KB |
test_06.txt | AC | 1434 ms | 256 KB |
test_07.txt | AC | 1730 ms | 256 KB |
test_08.txt | TLE | 2057 ms | 256 KB |
test_09.txt | TLE | 2103 ms | 256 KB |
test_10.txt | TLE | 2103 ms | 256 KB |
test_11.txt | TLE | 2103 ms | 256 KB |
test_12.txt | TLE | 2103 ms | 256 KB |
test_13.txt | AC | 560 ms | 256 KB |
test_14.txt | AC | 296 ms | 256 KB |
test_15.txt | TLE | 2098 ms | 256 KB |
test_16.txt | TLE | 2103 ms | 256 KB |
test_17.txt | TLE | 2103 ms | 256 KB |
test_18.txt | TLE | 2103 ms | 256 KB |
test_19.txt | TLE | 2103 ms | 256 KB |
test_20.txt | TLE | 2103 ms | 256 KB |
test_21.txt | TLE | 2103 ms | 256 KB |
test_22.txt | TLE | 2103 ms | 256 KB |
test_23.txt | TLE | 2103 ms | 256 KB |
test_24.txt | TLE | 2103 ms | 256 KB |
test_25.txt | AC | 24 ms | 256 KB |
test_26.txt | TLE | 2103 ms | 256 KB |
test_27.txt | TLE | 2103 ms | 256 KB |
test_28.txt | AC | 846 ms | 256 KB |
test_29.txt | TLE | 2103 ms | 256 KB |
test_30.txt | TLE | 2103 ms | 256 KB |
test_31.txt | TLE | 2103 ms | 256 KB |
test_32.txt | TLE | 2103 ms | 256 KB |
test_33.txt | TLE | 2103 ms | 256 KB |
test_34.txt | TLE | 2103 ms | 256 KB |
test_35.txt | TLE | 2103 ms | 256 KB |
test_36.txt | TLE | 2103 ms | 256 KB |
test_37.txt | TLE | 2103 ms | 256 KB |
test_38.txt | TLE | 2103 ms | 256 KB |
test_39.txt | TLE | 2103 ms | 256 KB |
test_40.txt | TLE | 2103 ms | 256 KB |
test_41.txt | TLE | 2103 ms | 256 KB |
test_42.txt | TLE | 2103 ms | 256 KB |
test_43.txt | TLE | 2103 ms | 256 KB |
test_44.txt | TLE | 2103 ms | 256 KB |
test_45.txt | TLE | 2103 ms | 256 KB |
test_46.txt | TLE | 2103 ms | 256 KB |
test_47.txt | TLE | 2103 ms | 256 KB |
test_48.txt | TLE | 2103 ms | 256 KB |
test_49.txt | TLE | 2103 ms | 256 KB |
test_50.txt | TLE | 2103 ms | 256 KB |
test_51.txt | TLE | 2103 ms | 256 KB |
test_52.txt | TLE | 2103 ms | 256 KB |
test_53.txt | TLE | 2103 ms | 256 KB |
test_54.txt | TLE | 2103 ms | 256 KB |
test_55.txt | TLE | 2103 ms | 256 KB |
test_56.txt | TLE | 2103 ms | 256 KB |
test_57.txt | TLE | 2103 ms | 256 KB |
test_58.txt | TLE | 2103 ms | 256 KB |
test_59.txt | TLE | 2103 ms | 256 KB |
test_60.txt | TLE | 2103 ms | 256 KB |
test_61.txt | TLE | 2103 ms | 256 KB |
test_62.txt | AC | 289 ms | 256 KB |
test_63.txt | TLE | 2103 ms | 256 KB |
test_64.txt | TLE | 2103 ms | 256 KB |
test_65.txt | TLE | 2103 ms | 256 KB |
test_66.txt | TLE | 2103 ms | 256 KB |
test_67.txt | TLE | 2103 ms | 256 KB |
test_68.txt | TLE | 2103 ms | 256 KB |
test_69.txt | TLE | 2103 ms | 256 KB |
test_70.txt | TLE | 2103 ms | 256 KB |