Submission #1160488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160488		8pete8	Lampice (COCI19_lampice)	C++17	42 / 110	5090 ms	16480 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=193;
//#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;
int inv(int x){
	int ex=mod-2,ans=1;
	while(ex){
		if(ex&1)ans=(ans*x)%mod;
		x=(x*x)%mod;
		ex>>=1;
	}
	return ans;
}
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;
}
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 dept[mxn+10],who[mxn+10];
bool dfs(int cur,int p){
	if(dept[cur]>target)return 0;
	up[cur]=p;
    who[dept[cur]]=cur;

	val[cur]=(val[p]+(a[cur-1]*P[dept[cur]])%mod)%mod;
	val2[cur]=((val2[p]*base)%mod+a[cur-1])%mod;

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

	int need=target-dept[cur]-1;
	if(dept[cur]+1>=need){
		int X=0;
		if(dept[cur]-need<0)X=0;
		else X=who[dept[cur]-need];
		if(yes[X]){
			g=((val[cur]-val[X]+mod)%mod*pinv[target-2*need])%mod;
			if(mp[g])return 1;
			upd2.pb(g);
		}
	}
	if(dept[cur]<=(target/2)+1){
		g=((val[cur]-a[node-1]+mod)%mod*pinv[1])%mod;
		if(lf[g])return 1;
		upd.pb(g);
	}
	for(auto i:adj[cur])if(i!=p&&!del[i]){
		dept[i]=dept[cur]+1;
		if(dfs(i,cur))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;
	who[0]=node;
	for(auto i:adj[node]){
		if(del[i])continue;
		dept[i]=1;
		if(dfs(i,node)){
			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=inv(base);
	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+1)/2;
		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:33:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   33 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
lampice.cpp:42:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   42 | void setIO(string name){
      |                       ^
lampice.cpp:51:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 | int inv(int x){
      |              ^
lampice.cpp:60:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   60 | 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];}
      |                         ^
lampice.cpp:61:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 | int getcen(int cur,int p,int need){
      |                                  ^
lampice.cpp:72:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   72 | bool dfs(int cur,int p){
      |                       ^
lampice.cpp:108:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  108 | bool solve(int cur){
      |                   ^
lampice.cpp:138:9: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  138 | void re(){
      |         ^
lampice.cpp:141:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  141 | int32_t main(){
      |              ^
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: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37