Submission #1511520
Source Code Expand
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) #define fore(i,a) for(auto &i:a) #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- #ifdef _MSC_VER #pragma push_macro("long") #undef long #ifdef _WIN32 inline unsigned int __builtin_ctz(unsigned int x) { unsigned long r; _BitScanForward(&r, x); return r; } inline unsigned int __builtin_clz(unsigned int x) { unsigned long r; _BitScanReverse(&r, x); return 31 - r; } inline unsigned int __builtin_ffs(unsigned int x) { unsigned long r; return _BitScanForward(&r, x) ? r + 1 : 0; } inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); } #ifdef _WIN64 inline unsigned long long __builtin_ctzll(unsigned long long x) { unsigned long r; _BitScanForward64(&r, x); return r; } inline unsigned long long __builtin_clzll(unsigned long long x) { unsigned long r; _BitScanReverse64(&r, x); return 63 - r; } inline unsigned long long __builtin_ffsll(unsigned long long x) { unsigned long r; return _BitScanForward64(&r, x) ? r + 1 : 0; } inline unsigned long long __builtin_popcountll(unsigned long long x) { return __popcnt64(x); } #else inline unsigned int hidword(unsigned long long x) { return static_cast<unsigned int>(x >> 32); } inline unsigned int lodword(unsigned long long x) { return static_cast<unsigned int>(x & 0xFFFFFFFF); } inline unsigned long long __builtin_ctzll(unsigned long long x) { return lodword(x) ? __builtin_ctz(lodword(x)) : __builtin_ctz(hidword(x)) + 32; } inline unsigned long long __builtin_clzll(unsigned long long x) { return hidword(x) ? __builtin_clz(hidword(x)) : __builtin_clz(lodword(x)) + 32; } inline unsigned long long __builtin_ffsll(unsigned long long x) { return lodword(x) ? __builtin_ffs(lodword(x)) : hidword(x) ? __builtin_ffs(hidword(x)) + 32 : 0; } inline unsigned long long __builtin_popcountll(unsigned long long x) { return __builtin_popcount(lodword(x)) + __builtin_popcount(hidword(x)); } #endif // _WIN64 #endif // _WIN32 #pragma pop_macro("long") #endif // _MSC_VER struct MaxClique { static const int MV = 210; int V, ans; int el[MV][MV / 30 + 1]; int dp[MV]; int s[MV][MV / 30 + 1]; vector<int> sol; void init(int v) { V = v; ans = 0; memset(el, 0, sizeof(int) * MV * (MV / 30 + 1)); memset(dp, 0, sizeof(int) * MV); } /* Zero Base */ void addEdge(int u, int v) { if (u > v) swap(u, v); if (u == v) return; el[u][v / 32] |= (1 << (v % 32)); } bool dfs(int v, int k) { int c = 0, d = 0; for (int i = 0; i<(V + 31) / 32; i++) { s[k][i] = el[v][i]; if (k != 1) s[k][i] &= s[k - 1][i]; c += __builtin_popcount(s[k][i]); } if (c == 0) { if (k > ans) { ans = k; sol.clear(); sol.push_back(v); return 1; } return 0; } for (int i = 0; i<(V + 31) / 32; i++) { for (int a = s[k][i]; a; d++) { if (k + (c - d) <= ans) return 0; int lb = a&(-a), lg = 0; a ^= lb; while (lb != 1) { lb = (unsigned int)(lb) >> 1; lg++; } int u = i * 32 + lg; if (k + dp[u] <= ans) return 0; if (dfs(u, k + 1)) { sol.push_back(v); return 1; } } } return 0; } int solve() { for (int i = V - 1; i >= 0; i--) { dfs(i, 1); dp[i] = ans; } return ans; } }; /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ MaxClique mc; int N, M; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; mc.init(N); rep(i, 0, N) { int x, y; cin >> x >> y; x--; y--; mc.addEdge(x, y); } cout << mc.solve() << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 派閥 |
User | hamayanhamayan |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 4429 Byte |
Status | RE |
Exec Time | 96 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 | 1 ms | 256 KB |
00_sample_02.txt | AC | 1 ms | 256 KB |
00_sample_03.txt | WA | 1 ms | 256 KB |
00_sample_04.txt | RE | 96 ms | 256 KB |
test_01.txt | RE | 96 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 | WA | 1 ms | 256 KB |
test_09.txt | WA | 1 ms | 256 KB |
test_10.txt | WA | 1 ms | 256 KB |
test_11.txt | AC | 1 ms | 256 KB |
test_12.txt | WA | 1 ms | 256 KB |
test_13.txt | AC | 1 ms | 256 KB |
test_14.txt | AC | 1 ms | 256 KB |
test_15.txt | WA | 1 ms | 256 KB |
test_16.txt | WA | 1 ms | 256 KB |
test_17.txt | WA | 1 ms | 256 KB |
test_18.txt | WA | 1 ms | 256 KB |
test_19.txt | WA | 1 ms | 256 KB |
test_20.txt | WA | 1 ms | 256 KB |
test_21.txt | WA | 1 ms | 256 KB |
test_22.txt | WA | 1 ms | 256 KB |
test_23.txt | WA | 1 ms | 256 KB |
test_24.txt | WA | 1 ms | 256 KB |
test_25.txt | RE | 96 ms | 256 KB |
test_26.txt | WA | 1 ms | 256 KB |
test_27.txt | WA | 1 ms | 256 KB |
test_28.txt | WA | 1 ms | 256 KB |
test_29.txt | WA | 1 ms | 256 KB |
test_30.txt | WA | 1 ms | 256 KB |
test_31.txt | WA | 1 ms | 256 KB |
test_32.txt | WA | 1 ms | 256 KB |
test_33.txt | WA | 1 ms | 256 KB |
test_34.txt | WA | 1 ms | 256 KB |
test_35.txt | WA | 1 ms | 256 KB |
test_36.txt | WA | 1 ms | 256 KB |
test_37.txt | AC | 1 ms | 256 KB |
test_38.txt | WA | 1 ms | 256 KB |
test_39.txt | WA | 1 ms | 256 KB |
test_40.txt | WA | 1 ms | 256 KB |
test_41.txt | WA | 1 ms | 256 KB |
test_42.txt | WA | 1 ms | 256 KB |
test_43.txt | WA | 1 ms | 256 KB |
test_44.txt | WA | 1 ms | 256 KB |
test_45.txt | WA | 1 ms | 256 KB |
test_46.txt | WA | 1 ms | 256 KB |
test_47.txt | WA | 1 ms | 256 KB |
test_48.txt | WA | 1 ms | 256 KB |
test_49.txt | WA | 1 ms | 256 KB |
test_50.txt | WA | 1 ms | 256 KB |
test_51.txt | WA | 1 ms | 256 KB |
test_52.txt | WA | 1 ms | 256 KB |
test_53.txt | WA | 1 ms | 256 KB |
test_54.txt | WA | 1 ms | 256 KB |
test_55.txt | WA | 1 ms | 256 KB |
test_56.txt | WA | 1 ms | 256 KB |
test_57.txt | WA | 1 ms | 256 KB |
test_58.txt | WA | 1 ms | 256 KB |
test_59.txt | WA | 1 ms | 256 KB |
test_60.txt | WA | 1 ms | 256 KB |
test_61.txt | WA | 1 ms | 256 KB |
test_62.txt | RE | 96 ms | 256 KB |
test_63.txt | WA | 1 ms | 256 KB |
test_64.txt | WA | 1 ms | 256 KB |
test_65.txt | WA | 1 ms | 256 KB |
test_66.txt | WA | 1 ms | 256 KB |
test_67.txt | WA | 1 ms | 256 KB |
test_68.txt | WA | 1 ms | 256 KB |
test_69.txt | WA | 1 ms | 256 KB |
test_70.txt | WA | 1 ms | 256 KB |