| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 921203 |
2024-02-03T13:41:38 Z |
8pete8 |
Lampice (COCI19_lampice) |
C++17 |
|
187 ms |
12176 KB |
#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
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++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
12056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
12176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
