제출 #1013174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013174		pan	Lampice (COCI19_lampice)	C++17	0 / 110	2 ms	6748 KiB

lampice

#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
// General
ll const P = 583726327;
ll const mod = 1000000007;
ll const MAXN = 50005;
ll n;
string s;

ll inv(ll a) {
    return a <= 1 ? a : mod - (ll)(mod / a) * inv(mod % a) % mod;
}


// hashing: string to integer

ll conv[50], val[MAXN], ph[MAXN], invph[MAXN];

// centroid decomposition

ll sub[MAXN], lvl[MAXN], par[MAXN], m[MAXN];
vector<ll> V[MAXN];

int dfs1(int u, int p, int l) {
	sub[u] = 1; // Subtree size is 1
	for (auto v : V[u]) {
		if (lvl[v] != -1) continue; // Already added to centroid tree
		if (v == p) continue;
		sub[u] += dfs1(v, u, l); // Increase size of subtree
	}
	return sub[u];
}
int dfs2(int u, int p, int n) { // Pass in the size of the subtree
	for (auto v : V[u]) {
		if (lvl[v] != -1) continue; // Already added to centroid tree
		if (v != p && sub[v] > n / 2) {
			return dfs2(v, u, n); // DFS to that node
		}
	}
	return u; // No child has size more than n/2, hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u, int p=  -1, int l = 0) {
	int n = dfs1(u, p, l); // Find the size of each subtree
	int cent = dfs2(u, p, n); // Find the centroid
	if (p == -1) p = cent; // Parent of root is yourself
	par[cent] = p; // Set the parent of centroid to the previous centroid
	lvl[cent] = l;
	for (auto v : V[cent]) {
		if (lvl[v] != -1) continue;
// If we have already added to centroid then we ignore
		build(v, cent, l + 1); // Recursively build each subtree
	}
}

//To construct the centroid tree, call build(root, -1, 0);



// precompute hash value

bool visited[MAXN];
ll locate[MAXN], up[MAXN], down[MAXN];
unordered_map<ll, unordered_map<ll, ll> > match[MAXN];

void mark(ll u, ll p, ll sub, ll cen, ll dep)
{
	if (visited[u]) return;
	locate[dep] = u;
	down[u] = (down[p] + ph[dep]*val[u]%mod)%mod;
	up[u] = (up[p]*P%mod + val[u])%mod;
	ll line = (down[u] - val[cen] + mod)*invph[1]%mod;
	if (match[cen][dep].count(line) &&match[cen][dep].count(line)!=sub )match[cen][dep][line] = -1;
	else match[cen][dep][line] = sub;
	for (ll x: V[u]) if (x!=p) mark(x, u, sub, cen,dep+1); 

}

void precompute()
{
	for (ll i=1; i<=n; ++i)
	{
		ll cur = i;
		match[i][0][0] = -1;
		down[i] = up[i] = val[i];
		locate[0] = i;
		while (par[cur]!=cur) {cur = par[cur], visited[cur] = 1;}
		for (ll u: V[i]) mark(u, i, u, i, 1);
		cur = i;
		while (par[cur]!=cur) cur = par[cur], visited[cur] = 0;
	}
}

// check whether palindrone of length x exists

bool search(ll u, ll p, ll sub, ll cen, ll dep, ll len)
{
	if (visited[u]) return 0;
	locate[dep] = u;
	down[u] = (down[p] + ph[dep]*val[u]%mod)%mod;
	up[u] = (up[p]*P%mod + val[u])%mod;
	if (len/2 <= dep && dep < len) // ensure that the other end pass trhough centroid
	{
		ll over = len - (dep + 1);
		ll pld = len - over*2;
		if (up[locate[pld-1]] == down[locate[pld-1]])
		{
			ll line = (down[u] - down[locate[pld-1]] + mod)*invph[pld]%mod;
			if (match[cen][over].count(line) && match[cen][over][line]!=sub) return 1;
		}
	}
	for (ll x: V[u]) if (x!=p && search(x, u, sub, cen,dep+1, len)) return 1;
	return 0;
	
	
}


bool check(ll x)
{
	if (x < 2) return 1;
	for (ll i=1; i<=n; ++i)
	{
		ll cur = i;
		down[i] = up[i] = val[i];
		locate[0] = i;
		while (par[cur]!=cur) cur = par[cur], visited[cur] = 1;
		for (ll u: V[i]) if (search(u, i, u, i, 1, x)) return 1;
		cur = i;
		while (par[cur]!=cur) cur = par[cur], visited[cur] = 0;
	}
	return 0;
}




int main()
{
	freopen("lampice_1.in", "r", stdin);
	// Input
	input(n);
	cin >> s;
	for (ll i=0; i<n-1; ++i)
	{
		ll u, v;
		input2(u, v);
		V[u].pb(v);
		V[v].pb(u);
	}
	// init
	for (ll i=0; i<30; ++i) {conv[i] = rnd()%mod;}
	for (ll i=0; i<n; ++i) val[i+1] = conv[s[i]-'a'];
	ph[0]=  invph[0] = 1;
	for (ll i=1; i<=n; ++i)
	{
		ph[i] = ph[i-1]*P%mod;
		invph[i] = inv(ph[i]);
	}
	fill(visited, visited+n+1, 0);
	memset(lvl, -1, sizeof lvl);
	build(1);
	precompute();
	// BSTA
	ll ans = 0;
	// Case1 : Even
	ll lo = 0, hi = n;
	while (lo!=hi)
	{
		ll mid = (lo+hi+1)/2;
		if (check(mid*2)) lo = mid;
		else hi = mid-1;
	}
	ans = max(ans, lo*2);
	// Case 2: Odd
	lo = 0, hi = n;
	while (lo!=hi)
	{
		ll mid = (lo+hi+1)/2;
		if (check(mid*2+1)) lo = mid;
		else hi = mid-1;
	}
	ans = max(ans, lo*2+1);
	print(ans, '\n');
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

lampice.cpp: In function 'void mark(ll, ll, ll, ll, ll)':
lampice.cpp:106:63: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long long int, long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  106 |  if (match[cen][dep].count(line) &&match[cen][dep].count(line)!=sub )match[cen][dep][line] = -1;
      |                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:173:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |  freopen("lampice_1.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define input(x) scanf("%lld", &x);
      |                  ~~~~~^~~~~~~~~~~~
lampice.cpp:175:2: note: in expansion of macro 'input'
  175 |  input(n);
      |  ^~~~~
lampice.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~
lampice.cpp:180:3: note: in expansion of macro 'input2'
  180 |   input2(u, v);
      |   ^~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37