Submission #1160460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160460		8pete8	Lampice (COCI19_lampice)	C++17	17 / 110	5093 ms	14608 KiB

lampice

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<complex>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
//#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
using namespace std;
using cd = complex<double>;
double const PI=acos(-1);
const int mod=1e9+7,mxn=1e5+5,inf=1e18,minf=-1e18,lg=15,base=19;
//#undef int
int k,m,n,q,d;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
vector<int>adj[mxn+10];
string a;
int del[mxn+10],sz[mxn+10];
int P[mxn+10],pinv[mxn+10],target;
void getsz(int cur,int p){sz[cur]=1;for(auto i:adj[cur])if(i!=p&&!del[i])getsz(i,cur),sz[cur]+=sz[i];}
int getcen(int cur,int p,int need){
	for(auto i:adj[cur])if(i!=p&&!del[i]){
		if(sz[i]>need/2)return getcen(i,cur,need);
	}
	return cur;
}
unordered_map<int,int>mp,lf;
vector<int>upd,upd2;
int node;
int up[mxn+10],val[mxn+10],val2[mxn+10],yes[mxn+10];
int nxt[mxn+10],dept[mxn+10];
bool dfs(int cur,int p,int Y,int X){
	up[cur]=p;

	val[cur]=(val[p]+(a[cur-1]*P[dept[cur]])%mod)%mod;
	val2[cur]=((val2[p]*base)%mod+a[cur-1])%mod;
	
	int g=((val[cur]-val[Y]+mod)%mod*pinv[dept[cur]-(dept[cur]+1)/2+1])%mod;
	if(dept[cur]%2==0)yes[cur]=(g==val2[up[Y]]);
	else yes[cur]=(g==val2[Y]);
	if(yes[cur]&&dept[cur]+1>=target)return 1;

	g=((val[cur]-a[node-1]+mod)%mod*pinv[1])%mod;
	if(lf[g])return 1;
	upd.pb(g);

	int need=target-dept[cur]-1;
	if(need<0)return 0;
	if(X==0&&dept[cur]>=need){
		X=node;
	}
	
	if(X){
		int c=0;
		while(dept[X]!=dept[cur]-need)X=nxt[X],c++;
		if(c>2)assert(0);
	}
	if(dept[cur]+1>=need){
		if(yes[X]){
			g=((val[cur]-val[X]+mod)%mod*pinv[target-2*need])%mod;
			if(mp[g])return 1;
			upd2.pb(g);
		}
	}
	for(auto i:adj[cur])if(i!=p&&!del[i]){
		nxt[cur]=i;
		dept[i]=dept[cur]+1;
		if(dfs(i,cur,((dept[cur]+1)%2)?Y:nxt[Y],nxt[X]))return 1;
	}
	return 0;
}
bool solve(int cur){
	getsz(cur,-1);
	node=getcen(cur,-1,sz[cur]);
	up[node]=dept[node]=0;
	val[node]=val2[node]=a[node-1];
	yes[node]=1;
	for(auto i:adj[node]){
		if(del[i])continue;
		nxt[node]=i;
		dept[i]=1;
		if(dfs(i,node,node,0)){
			upd.clear();
			upd2.clear();
			mp.clear();
			lf.clear();
			return 1;
		}
		for(auto j:upd)mp[j]=1;
		for(auto j:upd2)lf[j]=1;
		upd.clear();
		upd2.clear();
	}
	lf.clear();
	mp.clear();
	del[node]=1;
	for(auto i:adj[node])if(!del[i]){
		if(solve(i))return 1;
	}
	return 0;
}
void re(){
	for(int i=1;i<=n;i++)del[i]=0;
}
int32_t main(){
	fastio
	yes[0]=1;
	cin>>n>>a;
	P[0]=pinv[0]=1;
	int div=157894738;
	for(int i=1;i<=n;i++)P[i]=(P[i-1]*base)%mod,pinv[i]=(pinv[i-1]*div)%mod;
	for(int i=0;i<n-1;i++){
		int u,v;cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	int ans=minf;
	for(int k=0;k<2;k++){
		int l=1,r=n;
		while(l<=r){
			int mid=l+(r-l)/2;
			target=mid*2-k;
			if(solve(1)){
				l=mid+1,ans=max(ans,target);
			}
			else r=mid-1;
			re();
		}
	}
	ans=max(ans,1LL);
	cout<<ans;
}
/*

*/

Compilation message (stderr)

lampice.cpp: In function 'void setIO(std::string)':
lampice.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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