Submission #921203

#	Time	Username	Problem	Language	Result	Execution time	Memory
921203		8pete8	Lampice (COCI19_lampice)	C++17	0 / 110	187 ms	12176 KiB

lampice

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long
const int mxn=5e4+10,minf=-1e9,mod=1e9+7,inf=1e18,lg=60;
// take 0,1,2,3;
int sz[mxn+10];
vector<int>adj[mxn+10];
bool del[mxn+10];
int p[mxn+10],ans=1,h[mxn+10],val[mxn+10];
char col[mxn+10];
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]&&sz[i]*2>need)return getcen(i,cur,need);
	return cur;
}
int getval(int node){return ((col[node]-'a'+1)*p[h[node]])%mod;}
map<int,vector<pii>>mp;
void solve(int cur,int p,int deg){
	val[cur]=val[p]+getval(cur);
	mp[val[cur]].pb({deg,h[cur]});
	for(auto i:adj[cur]){
		if(i==p||del[i])continue;
		h[i]=h[cur]+1;
		solve(i,cur,deg);
	}
}
int inv(int a){
	int ex=mod-2;
	int b=a,ans=1;
	while(ex){
		if(ex&1)ans=(ans*b)%mod;
		b=(b*b)%mod;
		ex>>=1;
	}
	return ans;
}
int divi;
void decomp(int cur){
	getsz(cur,-1);
	int node=getcen(cur,-1,sz[cur]);
	mp.clear();
	h[node]=0;
	val[node]=0;
	int cnt=0;
	for(auto i:adj[node]){
		if(del[i])continue;
		h[i]=h[node]+1;
		solve(i,node,cnt++);
	}
	h[node]=1;
	int g=getval(node);
	for(auto i:mp){
		for(int j=1;j<i.s.size();j++)if(i.s[j-1].f!=i.s[j].f)ans=max(ans,i.s[j].s*2+1);
		for(int j=0;j<i.s.size();j++){
			if(col[adj[node][i.s[j].f]]==col[node]){
				ans=max(ans,2ll);
				int nv=((i.f-g)+mod)%mod;
				nv=(nv*divi)%mod;
				for(auto k:mp[nv])if(k.f!=i.s[j].f){
					ans=max(ans,i.s[j].s*2);
					break;
				}
			}
		}
	}
	del[node]=true;
	for(auto i:adj[node])if(!del[i])decomp(i);
}
int32_t main(){
	fastio
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>col[i];
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	p[0]=1;
	for(int i=1;i<=n;i++)p[i]=(p[i-1]*31)%mod;
	divi=inv(p[1]);
	decomp(1);
	cout<<ans;
}

Compilation message (stderr)

lampice.cpp: In function 'void decomp(long long int)':
lampice.cpp:82:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int j=1;j<i.s.size();j++)if(i.s[j-1].f!=i.s[j].f)ans=max(ans,i.s[j].s*2+1);
      |               ~^~~~~~~~~~~
lampice.cpp:83:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for(int j=0;j<i.s.size();j++){
      |               ~^~~~~~~~~~~

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