oj.uz

답안 #349732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349732 2021-01-18T09:40:50 Z arnold518 Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 21652 KB 
#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;
void dfs3(int now, int bef)
{
	ST.push_back(now);

	if(2*dep[now]-D>=0)
	{
		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;
		}
	}

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

void decomp(int now)
{
	getsz(now, now);
	now=getcen(now, now, sz[now]);
	del[now]=true;	

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

	M.clear();
	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();
	ST.push_back(now);
	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);
	}
	ST.clear();

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

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<=N; i++) ppow[i]=ppow[i-1]*P%MOD;
	for(int i=2; i<=N; 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;
	N=t;

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

Compilation message

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

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 4076 KB Output is correct
2 Runtime error 1914 ms 8172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5047 ms 21652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5051 ms 18320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 4076 KB Output is correct
2 Runtime error 1914 ms 8172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -