Submission #1511580
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 BitSet { enum { K = 2, W = 64 }; uint64_t data[K]; BitSet() : data{ 0 } {} explicit operator bool() const { uint64_t r = 0; rep(i, 0, K) r |= data[i]; return r != 0; } bool get(unsigned pos) const { return data[pos / W] >> (pos % W) & 1; } void set(unsigned pos) { data[pos / W] |= uint64_t(1) << (pos % W); } void unset(unsigned pos) { data[pos / W] &= ~(uint64_t(1) << (pos % W)); } int count() const { int res = 0; rep(i, 0, K) res += popcount(data[i]); return res; } BitSet operator&(BitSet that) const { BitSet res; rep(i, 0, K) res.data[i] = data[i] & that.data[i]; return res; } bool isIntersectTo(const BitSet &that) const { return bool(*this & that); } int getSingleton() const { rep(i, 0, K) if (data[i]) { if ((data[i] & (data[i] - 1)) != 0) return -1; for (int j = i + 1; j < K; ++j) if (data[j]) return -1; return i * W + bsf(data[i]); } return -1; } static int bsf(uint64_t x) { return __builtin_ctzll(x); } static int popcount(uint64_t x) { return __builtin_popcountll(x); } std::string toBitString() const { std::string res(128, '0'); for (int i = 0; i < 128; ++i) res[i] = '0' + get(i); return res; } }; class MaximumCliqueBranchAndBound { public: typedef uint8_t Vertex; BitSet maximumClique(const vector<BitSet> &originalGraph) { graph = originalGraph; int N = (int)graph.size(); levels.assign(N, BitSet()); vertexLevel.assign(N, -1); vertexDegree.assign(N, -1); BitSet initSet; for (int i = 0; i < N; ++i) initSet.set(i); globalBuffer.resize(N * N * 2 + N + N * 3 * N); levelVertices.resize(N); rep(i, 0, N) levelVertices[i].first = globalBuffer.data() + i * N; degreeVertices.resize(N); rep(i, 0, N) degreeVertices[i].first = globalBuffer.data() + (N + i) * N; Vertex *initOrder = globalBuffer.data() + N * N * 2, *nextBuffer = initOrder + N; rep(i, 0, N) initOrder[i] = i; curClique = maxClique = BitSet(); curSize = maxSize = 0; numRecs = 0; rec(initSet, initOrder, N, nextBuffer); //cerr << "numRecs = " << numRecs << endl; return maxClique; } private: void rec(BitSet remSet, const Vertex *originalOrder, int originalOrderSize, Vertex *buffer) { ++numRecs; int numLevels = 0, numVertices = 0; for (int ix = 0; ix < originalOrderSize; ++ix) { int p = originalOrder[ix]; if (!remSet.get(p)) continue; ++numVertices; int k = 0; while (k < numLevels && levels[k].isIntersectTo(graph[p])) ++k; if (k == numLevels) { levels[k] = BitSet(); ++numLevels; } levels[k].set(p); vertexLevel[p] = k; vertexDegree[p] = (remSet & graph[p]).count(); int threshold = maxSize - curSize; if (k > threshold && k == numLevels - 1) { reNumber(p, k, threshold); if (!levels[k]) --numLevels; } } Vertex *levelOrder = buffer, *levelOffsets = levelOrder + numVertices, *degreeOrder = levelOffsets + numLevels, *nextBuffer = degreeOrder + numVertices; for (int k = 0; k < numLevels; ++k) levelVertices[k].second = 0; for (int d = 0; d < numVertices; ++d) degreeVertices[d].second = 0; for (int ix = 0; ix < originalOrderSize; ++ix) { int v = originalOrder[ix]; if (remSet.get(v)) { { auto &p = levelVertices[vertexLevel[v]]; p.first[p.second++] = v; } { auto &p = degreeVertices[vertexDegree[v]]; p.first[p.second++] = v; } } } for (int k = 0, num = 0; k < numLevels; ++k) { levelOffsets[k] = num; auto p = levelVertices[k]; for (int i = 0; i < p.second; ++i) levelOrder[num++] = p.first[i]; } for (int d = numVertices - 1, num = 0; d >= 0; --d) { auto p = degreeVertices[d]; for (int i = 0; i < p.second; ++i) degreeOrder[num++] = p.first[i]; } for (int i = numVertices; ; --i) { int threshold = max(maxSize - curSize, 0); if (threshold >= numLevels || i <= levelOffsets[threshold]) break; int u = levelOrder[i - 1]; curClique.set(u), ++curSize; BitSet newSet = remSet & graph[u]; if (newSet) { rec(newSet, degreeOrder, numVertices, nextBuffer); } else if (curSize > maxSize) { maxClique = curClique, maxSize = curSize; } curClique.unset(u), --curSize; remSet.unset(u); } } void reNumber(int p, int k, int threshold) { for (int i = 0; i < threshold; ++i) { BitSet S = graph[p] & levels[i]; int q = S.getSingleton(); if (q == -1) continue; for (int j = i + 1; j <= threshold; ++j) { if (graph[q] & levels[j]) continue; levels[k].unset(p); levels[i].unset(q); levels[i].set(p); levels[j].set(q); vertexLevel[p] = i; vertexLevel[q] = j; return; } } } vector<BitSet> graph; BitSet curClique, maxClique; int curSize, maxSize; vector<BitSet> levels; vector<int> vertexLevel, vertexDegree; vector<pair<Vertex*, int>> levelVertices; vector<pair<Vertex*, int>> degreeVertices; vector<Vertex> globalBuffer; long long numRecs; }; /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N, M; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; vector<BitSet> g(N); rep(i, 0, M) { int x, y; cin >> x >> y; x--; y--; g[x].set(y); g[y].set(x); } MaximumCliqueBranchAndBound mc; BitSet ans = mc.maximumClique(g); cout << ans.count() << endl; }
Submission Info
Submission Time | |
---|---|
Task | D - 派閥 |
User | hamayanhamayan |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 9790 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 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 | 1 ms | 256 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 | 256 KB |
test_18.txt | AC | 1 ms | 256 KB |
test_19.txt | AC | 1 ms | 256 KB |
test_20.txt | AC | 1 ms | 256 KB |
test_21.txt | AC | 1 ms | 256 KB |
test_22.txt | AC | 1 ms | 256 KB |
test_23.txt | AC | 1 ms | 256 KB |
test_24.txt | AC | 1 ms | 256 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 | 256 KB |
test_35.txt | AC | 1 ms | 256 KB |
test_36.txt | AC | 1 ms | 256 KB |
test_37.txt | AC | 1 ms | 256 KB |
test_38.txt | AC | 1 ms | 256 KB |
test_39.txt | AC | 1 ms | 256 KB |
test_40.txt | AC | 1 ms | 256 KB |
test_41.txt | AC | 1 ms | 256 KB |
test_42.txt | AC | 1 ms | 256 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 | 256 KB |
test_48.txt | AC | 1 ms | 256 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 | 256 KB |
test_58.txt | AC | 1 ms | 256 KB |
test_59.txt | AC | 1 ms | 256 KB |
test_60.txt | AC | 1 ms | 256 KB |
test_61.txt | AC | 1 ms | 256 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 |