QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#193724#7514. Clique Challengeucup-team896#RE 1ms9788kbC++238.6kb2023-09-30 17:46:282023-09-30 17:46:29

Judging History

你现在查看的是最新测评结果

  • [2023-09-30 17:46:29]
  • 评测
  • 测评结果：RE
  • 用时：1ms
  • 内存：9788kb
查看
  • [2023-09-30 17:46:28]
  • 提交

answer

/*
 * @Author:             cmk666
 * @Created time:       2023-09-30 16:21:23
 * @Last Modified time: 2023-09-30 17:46:18
 */
#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
#ifdef LOCAL
#include"debug.h"
#else
#define D(...) ((void)0)
#endif
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
namespace FastIO
{
// ------------------------------
// #define IN_HAS_NEG
// #define OUT_HAS_NEG
// #define CHK_EOF
// #define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined(_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
	inline char gc() { return getchar(); }
	inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
	INLINE_V constexpr int _READ_SIZE = 1 << 18;
	INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
	inline char gc()
	{
		if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
		{
			_read_ptr = _read_buffer;
			_read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
			if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
		}
		return *_read_ptr++;
	}
#else
	INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
	inline char gc() { return *_read_ptr++; }
#endif
	INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
	INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
	inline void pc(char c)
	{
		*_write_ptr++ = c;
		if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
		{
			fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
			_write_ptr = _write_buffer;
		}
	}
	INLINE_V struct _auto_flush
	{
		inline ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
	}	_auto_flush;
#endif
#ifdef CHK_EOF
	inline constexpr bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
	inline constexpr bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
	inline constexpr bool _isdigit(char c) { return c & 16; }
	inline constexpr bool _isgraph(char c) { return c > 32; }
#endif
	template < class T >
	INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
	template < class T >
	INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
	template < class T >
	INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
	template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
	template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
	template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
	template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
	inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
	inline void read_cstr(char *s)
	{
		char c = gc(); while ( !_isgraph(c) ) c = gc();
		while ( _isgraph(c) ) *s++ = c, c = gc();
		*s = 0;
	}
	inline void read(string &s)
	{
		char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
		while ( _isgraph(c) ) s.push_back(c), c = gc();
	}
#ifdef IN_HAS_NEG
	template < class T, enable_if_t < _is_signed < T >, int > = 0 >
	inline void read(T &x)
	{
		char c = gc(); bool f = true; x = 0;
		while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
		if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
		else     while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
	}
	template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
	template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
	inline void read(T &x)
	{
		char c = gc(); while ( !_isdigit(c) ) c = gc();
		x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
	}
	inline void write(char c) { pc(c); }
	inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
	inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
	template < class T, enable_if_t < _is_signed < T >, int > = 0 >
	inline void write(T x)
	{
		char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
		if ( x >= 0 )  do buffer[digits++] =  ( x % 10 ) | 48, x /= 10; while ( x );
		else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
		while ( digits ) pc(buffer[--digits]);
	}
	template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
	template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
	inline void write(T x)
	{
		char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
		do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
		while ( digits ) pc(buffer[--digits]);
	}
	template < int N > struct _tuple_io_helper
	{
		template < class ...T >
		static inline void _read(tuple < T... > &x)
		{ _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
		template < class ...T >
		static inline void _write(const tuple < T... > &x)
		{ _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
	};
	template <> struct _tuple_io_helper < 1 >
	{
		template < class ...T >
		static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
		template < class ...T >
		static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
	};
	template < class ...T >
	inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
	template < class ...T >
	inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
	template < class T1, class T2 >
	inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
	template < class T1, class T2 >
	inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
	template < class T1, class ...T2 >
	inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
	template < class ...T >
	inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
	template < class T1, class ...T2 >
	inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
	template < class ...T >
	inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
	template < class T >
	inline void print(const T &x) { write(x); }
	inline void print_cstr(const char *x) { write_cstr(x); }
	template < class T1, class ...T2 >
	inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
	template < class ...T >
	inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
	inline void println() { pc(10); }
	inline void println_cstr() { pc(10); }
	template < class ...T >
	inline void println(const T &...x) { print(x...), pc(10); }
	template < class ...T >
	inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
int n, m, u, v, d[1009], id[1009], nw[1009], l;
int a[1 << 22], b[1 << 22], ea[29], eb[29], ec[29], e[1 << 22], la, lb;
bool g[1009][1009]; ll ans;
int main()
{
	read(n, m);
	For(i, 1, m) read(u, v), g[u][v] = g[v][u] = true, d[u]++, d[v]++;
	iota(id + 1, id + n + 1, 1), sort(id + 1, id + n + 1, [&](int x, int y) { return d[x] > d[y]; });
	For(i, 1, n)
	{
		*nw = id[i], l = 1;
		For(j, i + 1, n) if ( g[id[i]][id[j]] ) nw[l++] = id[j];
		fill(e, e + l, 0), la = ( l + 1 ) / 2, lb = l - la;
		fill(ea, ea + la, 0), fill(eb, eb + lb, 0), fill(ec, ec + la, 0);
		fill(a, a + ( 1 << la ), 0), fill(b, b + ( 1 << lb ), 0), *a = *b = 1, *e = ( 1 << lb ) - 1;
		For(j, 0, la - 1) For(k, 0, la - 1)
			if ( j == k || g[nw[j]][nw[k]] ) ea[j] |= 1 << k;
		For(j, 0, lb - 1) For(k, 0, lb - 1)
			if ( j == k || g[nw[j + la]][nw[k + la]] ) eb[j] |= 1 << k;
		For(j, 0, la - 1) For(k, 0, lb - 1)
			if ( g[nw[j]][nw[k + la]] ) ec[j] |= 1 << k;
		For(j, 1, ( 1 << la ) - 1)
		{
			u = j ^ ( j & -j ), v = __lg(j & -j);
			if ( a[u] && ( ea[v] & u ) == u ) a[j] = 1;
			e[j] = e[u] & ec[v];
		}
		For(j, 1, ( 1 << lb ) - 1)
		{
			u = j ^ ( j & -j ), v = __lg(j & -j);
			if ( b[u] && ( eb[v] & u ) == u ) b[j] = 1;
		}
		For(j, 0, lb - 1) For(k, 0, ( 1 << lb ) - 1)
			if ( !( k & ( 1 << j ) ) ) b[k | ( 1 << j )] += b[k];
		For(j, 0, ( 1 << la ) - 1) if ( j & 1 ) ans += a[j] * b[e[j]];
	}
	return println(ans), 0;
}
// 想上GM捏 想上GM捏 想上GM捏 想上GM捏 想上GM捏
// 伊娜可爱捏 伊娜贴贴捏
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9740kb

input:

3 2
1 2
2 3

output:

5

result:

ok single line: '5'

Test #2:

score: 0
Accepted
time: 0ms
memory: 9788kb

input:

3 3
1 2
1 3
2 3

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 1ms
memory: 7900kb

input:

1000 100
446 789
167 547
254 777
777 185
33 446
777 847
185 877
757 167
72 383
847 446
254 478
959 185
757 446
847 959
959 167
757 847
747 757
446 167
989 757
547 777
33 747
33 254
254 843
33 547
446 980
877 205
185 72
980 959
33 205
877 757
33 847
478 843
757 478
167 877
72 789
877 959
980 478
167 ...

output:

1373

result:

ok single line: '1373'

Test #4:

score: -100
Runtime Error

input:

1000 1000
770 105
219 498
686 498
343 534
15 591
919 588
149 588
298 915
551 523
710 116
105 637
523 991
343 476
145 420
604 588
254 120
551 421
476 298
900 710
915 343
445 421
986 867
445 588
219 356
919 105
584 875
991 604
776 919
588 254
919 421
356 348
105 551
15 113
919 15
356 523
343 155
770 9...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-04 15:30:17 | OpenSource Project