QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#192851#7513. Palindromic Beadsucup-team896#RE 3ms32964kbC++2310.6kb2023-09-30 15:40:252023-09-30 15:40:26

Judging History

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

  • [2024-03-27 16:34:54]
  • hack成功，自动添加数据
  • (/hack/584)
  • [2024-03-27 16:18:45]
  • hack成功，自动添加数据
  • (/hack/583)
  • [2023-09-30 15:40:26]
  • 评测
  • 测评结果：RE
  • 用时：3ms
  • 内存：32964kb
查看
  • [2023-09-30 15:40:25]
  • 提交

answer

/*
 * @Author:             cmk666
 * @Created time:       2023-09-30 15:08:08
 * @Last Modified time: 2023-09-30 15:40:05
 */
#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, u, v, a[200009], dfn[200009], nfd[200009], cnt, ans = 1, d[200009], fa[19][200009];
vector < int > g[200009], pos[200009], id; int dp[200009], di[200009];
inline void dfs(int u, int fa = 0)
{
	dfn[u] = ++cnt, ::fa[0][u] = fa, d[u] = d[fa] + 1;
	for ( int i : g[u] ) if ( i != fa ) dfs(i, u);
	nfd[u] = cnt;
}
inline int lca(int u, int v)
{
	if ( d[u] > d[v] ) swap(u, v);
	Fol(i, 18, 0) if ( d[fa[i][v]] >= d[u] ) v = fa[i][v];
	if ( u == v ) return u;
	Fol(i, 18, 0) if ( fa[i][u] != fa[i][v] ) u = fa[i][u], v = fa[i][v];
	return fa[0][u];
}
inline int dis(int u, int v) { return d[u] + d[v] - d[lca(u, v)] * 2; }
inline bool anc(int u, int v)
{
	Fol(i, 18, 0) if ( d[fa[i][v]] >= d[u] ) v = fa[i][v];
	return u == v;
}
inline int kth(int u, int k)
{
	Fol(i, 18, 0) if ( k & ( 1 << i ) ) u = fa[i][u];
	return u;
}
namespace ST_
{
	struct node
	{
		int lc, rc, v;
	}	t[10000009]; int cnt;
	inline int &lc(int x) { return t[x].lc; }
	inline int &rc(int x) { return t[x].rc; }
	inline int md(int x, int y) { return ( x + y ) >> 1; }
	inline void pu(int p) { t[p].v = max(t[lc(p)].v, t[rc(p)].v); }
	inline void modify(int &p, int l, int r, int pos, int v)
	{
		if ( !p ) p = ++cnt;
		if ( l == r ) { t[p].v = max(t[p].v, v); return; }
		pos <= md(l, r) ? modify(lc(p), l, md(l, r), pos, v)
						: modify(rc(p), md(l, r) + 1, r, pos, v), pu(p);
	}
	inline int qry(int p, int l, int r, int lp, int rp)
	{
		if ( !p || l > rp || r < lp ) return 0;
		if ( lp <= l && r <= rp ) return t[p].v;
		return max(qry(lc(p), l, md(l, r), lp, rp), qry(rc(p), md(l, r) + 1, r, lp, rp));
	}
}
namespace ST
{
	struct node
	{
		int rt;
	}	t[200009 << 2];
	inline int lc(int x) { return x << 1; }
	inline int rc(int x) { return lc(x) | 1; }
	inline int md(int x, int y) { return ( x + y ) >> 1; }
	inline void modify(int p, int l, int r, int pos, int pos_, int v)
	{
		ST_::modify(t[p].rt, 1, n, pos_, v);
		if ( l == r ) return;
		pos <= md(l, r) ? modify(lc(p), l, md(l, r), pos, pos_, v)
						: modify(rc(p), md(l, r) + 1, r, pos, pos_, v);
	}
	inline int qry(int p, int l, int r, int lp, int rp, int lp_, int rp_)
	{
		if ( l > rp || r < lp ) return 0;
		if ( lp <= l && r <= rp ) return ST_::qry(t[p].rt, 1, n, lp_, rp_);
		return max(qry(lc(p), l, md(l, r), lp, rp, lp_, rp_), qry(rc(p), md(l, r) + 1, r, lp, rp, lp_, rp_));
	}
}
inline void mdf(int pos, int pos_, int v) { ST::modify(1, 1, n, pos, pos_, v); }
inline int qry(int lp, int rp, int lp_, int rp_) { return ST::qry(1, 1, n, lp, rp, lp_, rp_); }
int main()
{
	read(n);
	For(i, 1, n) read(a[i]), pos[a[i]].push_back(i);
	For(i, 2, n) read(u, v), g[u].push_back(v), g[v].push_back(u);
	dfs(1);
	For(i, 1, 18) For(j, 1, n) fa[i][j] = fa[i - 1][fa[i - 1][j]];
	For(i, 1, n) if ( (int)pos[i].size() == 2 )
	{
		id.push_back(i), di[i] = dis(pos[i][0], pos[i][1]);
		if ( dfn[pos[i][0]] > dfn[pos[i][1]] ) swap(pos[i][0], pos[i][1]);
	}
	sort(id.begin(), id.end(), [&](int x, int y) { return di[x] > di[y]; });
	for ( int i : id )
	{
		if ( anc(pos[i][0], pos[i][1]) )
			u = kth(pos[i][1], d[pos[i][1]] - d[pos[i][0]] - 1),
			dp[i] = max(qry(1, dfn[u] - 1, dfn[pos[i][1]], nfd[pos[i][1]]),
						qry(dfn[pos[i][1]], nfd[pos[i][1]], nfd[u] + 1, n));
		else dp[i] = qry(dfn[pos[i][0]], nfd[pos[i][0]], dfn[pos[i][1]], nfd[pos[i][1]]);
		mdf(dfn[pos[i][0]], dfn[pos[i][1]], dp[i] += 2), ans = max(ans, dp[i] + ( di[i] > 1 ));
	}
	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: 3ms
memory: 30212kb

input:

4
1 1 2 2
1 2
2 3
2 4

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 2ms
memory: 32332kb

input:

5
1 3 2 2 1
1 2
2 3
3 4
4 5

output:

4

result:

ok single line: '4'

Test #3:

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

input:

6
1 1 2 2 3 3
1 2
2 3
3 4
4 5
5 6

output:

2

result:

ok single line: '2'

Test #4:

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

input:

6
1 2 3 4 5 6
1 2
2 3
3 4
4 5
5 6

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 3ms
memory: 32964kb

input:

2000
845 1171 345 282 1181 625 754 289 681 493 423 840 1494 318 266 1267 967 379 135 14 39 191 60 972 116 1216 1205 19 194 185 1360 861 379 430 1262 1151 756 65 389 488 277 53 1283 1438 101 1465 195 714 737 980 80 298 961 1326 163 1163 1317 1152 992 35 334 802 1502 486 710 234 555 88 1278 146 46 696...

output:

5

result:

ok single line: '5'

Test #6:

score: -100
Runtime Error

input:

200000
48015 47923 20609 71806 43752 68214 95683 89449 25809 58110 19878 52931 7845 45206 86245 82945 62977 37876 12456 105915 10509 92943 66950 88545 26442 26545 42278 66977 3970 9631 21524 43638 7979 58240 25719 56260 276 89721 9553 16550 52161 30307 82748 108443 36676 48581 59069 57412 62453 7965...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-12-09 02:01:49 | OpenSource Project