Submission #349810

#	Time	Username	Problem	Language	Result	Execution time	Memory
349810		arnold518	Lampice (COCI19_lampice)	C++14	0 / 110	5100 ms	22444 KiB

lampice

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 15e4;
const ll P = 31;
const ll MOD = 998244353;

ll mypow(ll x, ll y, ll m)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1, m)*x%m;
	ll t=mypow(x, y/2, m);
	return t*t%m;
}

ll inv(ll x, ll m)
{
	return mypow(x, m-2, m);
}

int N;
vector<int> adj[MAXN+10];
char S[MAXN+10];

int D;
bool flag=false;

int sz[MAXN+10], del[MAXN+10];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		getsz(nxt, now);
		sz[now]+=sz[nxt];
	}
}

int getcen(int now, int bef, int S)
{
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(del[nxt]) continue;
		if(sz[nxt]>S/2) return getcen(nxt, now, S);
	}
	return now;
}

int par[MAXN+10];
ll ppow[MAXN+10], ippow[MAXN+10];
int dep[MAXN+10];
ll H[MAXN+10], IH[MAXN+10];

void dfs(int now, int bef, int d)
{
	par[now]=bef;
	dep[now]=d;
	H[now]=(H[bef]+ppow[d]*(S[now]-'a'+1)%MOD)%MOD;
	IH[now]=(IH[bef]+ippow[d]*(S[now]-'a'+1)%MOD)%MOD;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
	}
}

ll geth(int u, int v)
{
	ll ret=0;
	if(dep[u]<dep[v])
	{
		ret=((H[v]-H[par[u]])%MOD+MOD)%MOD;
		ret=ret*ippow[dep[u]]%MOD;
	}
	else
	{
		ret=((IH[u]-IH[par[v]])%MOD+MOD)%MOD;
		ret=ret*ppow[dep[u]]%MOD;
	}
	return ret;
}

unordered_set<ll> M;

void dfs2(int now, int bef, int root)
{
	M.insert(geth(root, now));
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs2(nxt, now, root);
	}
}
	
vector<int> ST;
int dfs3(int now, int bef)
{
	if(dep[now]>D) return 0;
	ST.push_back(now);

	if(2*dep[now]-D>=0 && 2*dep[now]-D+1<ST.size())
	{
		if(geth(ST[0], ST[2*dep[now]-D])==geth(ST[2*dep[now]-D], ST[0]) && M.find(geth(ST[2*dep[now]-D+1], now))!=M.end())
		{
			//printf("%d / %d %d\n", now, D, dep[now]);
			flag=true;
			return 1;
		}
	}

	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(dfs3(nxt, now)) return 1;
	}
	ST.pop_back();
	return 0;
}

void decomp(int now)
{
	getsz(now, now);
	//printf("%d\n", sz[now]);
	now=getcen(now, now, sz[now]);
	del[now]=true;	

	dfs(now, 0, 0);
	//printf("CENTROID %d\n", now);

	ST.push_back(now);
	for(int i=0; i<adj[now].size(); i++)
	{
		int nxt=adj[now][i];
		if(del[nxt]) continue;
		dfs3(nxt, now);
		dfs2(nxt, now, nxt);
	}

	M.clear();
	if(flag)
	{
		ST.clear();
		return;
	}

	for(int i=adj[now].size()-1; i>=0; i--)
	{
		int nxt=adj[now][i];
		if(del[nxt]) continue;
		dfs3(nxt, now);
		dfs2(nxt, now, nxt);
	}
	M.clear();
	if(flag)
	{
		ST.clear();
		return;
	}
	ST.clear();

	for(int nxt : adj[now])
	{
		if(del[nxt]) continue;
		decomp(nxt);
		if(flag) return;
	}
}

bool solve(int x)
{
	D=x;
	flag=false;
	for(int i=1; i<=N; i++) del[i]=0;
	decomp(1);
	return flag;
}

int main()
{
	scanf("%d", &N);

	ppow[0]=1; ippow[0]=1;
	ppow[1]=P; ippow[1]=inv(P, MOD);
	for(int i=2; i<=MAXN; i++) ppow[i]=ppow[i-1]*P%MOD;
	for(int i=2; i<=MAXN; i++) ippow[i]=ippow[i-1]*ippow[1]%MOD;

	scanf(" %s", S+1);
	for(int i=1; i<N; i++)
	{
		int u, v, w=N+i;
		scanf("%d%d", &u, &v);
		adj[u].push_back(w);
		adj[w].push_back(u);
		adj[v].push_back(w);
		adj[w].push_back(v);
		//printf("%d %d\n", u, w);
		//printf("%d %d\n", v, w);
	}
	int t=N+N-1;
	for(int i=1; i<=N; i++)
	{
		if(adj[i].size()==1)
		{
			int u=++t, v=i;
			adj[u].push_back(v);
			adj[v].push_back(u);
			//printf("%d %d\n", u, v);
		}
	}
	for(int i=N+1; i<=t; i++) S[i]='z'+1;

	int lo=1, hi=N+1;

	N=t;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(solve(mid*2)) lo=mid;
		else hi=mid;
	}
	printf("%d\n", lo);
}

Compilation message (stderr)

lampice.cpp: In function 'int dfs3(int, int)':
lampice.cpp:109:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  if(2*dep[now]-D>=0 && 2*dep[now]-D+1<ST.size())
      |                        ~~~~~~~~~~~~~~^~~~~~~~~~
lampice.cpp: In function 'void decomp(int)':
lampice.cpp:139:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for(int i=0; i<adj[now].size(); i++)
      |               ~^~~~~~~~~~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:225:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  225 |   int mid=lo+hi>>1;
      |           ~~^~~
lampice.cpp:188:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  188 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
lampice.cpp:195:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  195 |  scanf(" %s", S+1);
      |  ~~~~~^~~~~~~~~~~~
lampice.cpp:199:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  199 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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