#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
struct pal_tree_node
{
int dlug;
long long hasz;
pal_tree_node *shrt[2], *syn[2];
pal_tree_node(int xd,long long hz)
{
dlug=xd;
hasz=hz;
shrt[0]=shrt[1]=syn[0]=syn[1]=NULL;
}
};
struct lista
{
int wart;
int l, r;
lista(int a)
{
wart=a;
l=-1;
r=-1;
}
lista()
{
wart=0;
l=-1;
r=-1;
}
};
vector<int>nal;
vector<bool>seq;
vector<pal_tree_node*>pref,suf;
pal_tree_node* pust;
pal_tree_node* jz[2];
void ini(int n)
{
nal.resize(n);
seq.resize(n);
pref.resize(n);
suf.resize(n);
pust = new pal_tree_node(0,0);
jz[0] = new pal_tree_node(1,50000000000001);
jz[1] = new pal_tree_node(1,50000000000002);
jz[0]->shrt[0]=jz[1]->shrt[1]=pust;
}
int znajdz(int ter)
{
if(nal[ter]==ter)
return ter;
nal[ter]=znajdz(nal[ter]);
return nal[ter];
}
int main()
{
ios_base::sync_with_stdio(0);
int n;
cin>>n;
ini(n);
vector<lista>akt_ciag(n);
vector<pair<int,int>>po(n);
vector<int>wielk(n,1);
vector<unordered_map<long long,bool>>mapy(n);
vector<vector<long long>>tusa(n);
vector<int>konc(n),gdzie_w_konc(n);
for(int i=0;i<n;++i)
{
char wcz;
cin>>wcz;
wcz-='0';
seq[i]=wcz;
nal[i]=i;
pref[i]=suf[i]=jz[wcz];
akt_ciag[i].l=akt_ciag[i].r=-1;
akt_ciag[i].wart=i;
po[i].first=po[i].second=i;
tusa[i].push_back(wcz+1);
mapy[i][wcz+1]=1;
}
vector<pair<int,int>>zlacz(n-1);
for(int ile_merge=0;ile_merge<n-1;++ile_merge)
{
cin>>zlacz[ile_merge].first>>zlacz[ile_merge].second;
--zlacz[ile_merge].first; --zlacz[ile_merge].second;
int a,b;
a=zlacz[ile_merge].first; b=zlacz[ile_merge].second;
a=znajdz(a);
b=znajdz(b);
akt_ciag[po[a].second].r=po[b].first;
akt_ciag[po[b].first].l=po[a].second;
po[a].second=po[b].second;
nal[b]=a;
}
int tut=po[znajdz(0)].first;
for(int i=0;i<n;++i)
{
gdzie_w_konc[tut]=i;
konc[i]=tut;
po[tut].first=po[tut].second=i;
tut=akt_ciag[tut].r;
}
for(int i=0;i<n;++i)
{
akt_ciag[i].l=akt_ciag[i].r=-1;
nal[i]=i;
po[i].first=po[i].second=gdzie_w_konc[i];
}
for(int ile_merge=0;ile_merge<n-1;++ile_merge)
{
int a,b;
a=zlacz[ile_merge].first; b=zlacz[ile_merge].second;
a=znajdz(a);
b=znajdz(b);
if(wielk[a]<=wielk[b])
{
pal_tree_node* najd=pref[b];
for(int i=po[a].second;i>=po[a].first;--i)
{
if(najd->dlug==po[b].second-i)
{
najd=najd->shrt[seq[konc[i]]];
if(najd==NULL)
najd=pust;
}
if(najd->dlug!=0)
if(seq[konc[i+1+(najd->dlug)]]!=seq[konc[i]])
{
najd=najd->shrt[seq[konc[i]]];
if(najd==NULL)
najd=pust;
}
if(najd->dlug==0)
{
if(seq[konc[i+1]]==seq[konc[i]])
{
//dwie takie same
if(pust->syn[seq[konc[i]]]==NULL)
{
pal_tree_node* pom= new pal_tree_node(2,(seq[konc[i]]+1)*4);
pust->syn[seq[konc[i]]]=pom;
pom->shrt[seq[konc[i]]]=jz[seq[konc[i]]];
}
najd=pust->syn[seq[konc[i]]];
if(mapy[b][(seq[konc[i]]+1)*4]!=1)
{
mapy[b][(seq[konc[i]]+1)*4]=1;
tusa[b].push_back((seq[konc[i]]+1)*4);
}
}
else
{
//jeden taki sam
najd=jz[seq[konc[i]]];
if(mapy[b][seq[konc[i]]+1]!=1)
{
mapy[b][seq[konc[i]]+1]=1;
tusa[b].push_back(seq[konc[i]]+1);
}
}
}
else
{
//dodajemy normalnie
if(najd->syn[seq[konc[i]]]==NULL)
{
//dodaj wierz
pal_tree_node* pom= new pal_tree_node((najd->dlug)+2,(najd->hasz)*3+seq[konc[i]]+1);
najd->syn[seq[konc[i]]]=pom;
//znajdz pom->shrt
pal_tree_node* pom2=najd->shrt[seq[konc[i]]];
if(pom2==NULL)
pom2=jz[seq[konc[i]]];
else
pom2=pom2->syn[seq[konc[i]]];
//no i teraz musze wiedziec co jest po nim
int x=seq[konc[i+pom2->dlug]];
pom->shrt[x]=pom2;
pom2=pom2->shrt[1-x];
pom->shrt[1-x]=pom2;
}
najd=najd->syn[seq[konc[i]]];
if(mapy[b][najd->hasz]!=1)
{
mapy[b][najd->hasz]=1;
tusa[b].push_back(najd->hasz);
}
}
//sprawdz czy najd jest sufixem b
if(najd->dlug==po[b].second-i+1)
suf[b]=najd;
}
pref[b]=najd;
po[b].first=po[a].first;
nal[a]=b;
for(auto i:tusa[a])
{
if(mapy[b][i]!=1)
{
mapy[b][i]=1;
tusa[b].push_back(i);
}
}
a=b;
}
else
{
pal_tree_node* najd=suf[a];
for(int i=po[b].first;i<=po[b].second;++i)
{
if(najd->dlug==i-po[a].first)
{
najd=najd->shrt[seq[konc[i]]];
if(najd==NULL)
najd=pust;
}
if(najd->dlug!=0)
if(seq[konc[i-1-(najd->dlug)]]!=seq[konc[i]])
{
najd=najd->shrt[seq[konc[i]]];
if(najd==NULL)
najd=pust;
}
if(najd->dlug==0)
{
if(seq[konc[i-1]]==seq[konc[i]])
{
//dwie takie same
if(pust->syn[seq[konc[i]]]==NULL)
{
pal_tree_node* pom= new pal_tree_node(2,(seq[konc[i]]+1)*4);
pust->syn[seq[konc[i]]]=pom;
pom->shrt[seq[konc[i]]]=jz[seq[konc[i]]];
}
najd=pust->syn[seq[konc[i]]];
if(mapy[a][(seq[konc[i]]+1)*4]!=1)
{
mapy[a][(seq[konc[i]]+1)*4]=1;
tusa[a].push_back((seq[konc[i]]+1)*4);
}
}
else
{
//jeden taki sam
najd=jz[seq[konc[i]]];
if(mapy[a][seq[konc[i]]+1]!=1)
{
mapy[a][seq[konc[i]]+1]=1;
tusa[a].push_back(seq[konc[i]]+1);
}
}
}
else
{
//dodajemy normalnie
if(najd->syn[seq[konc[i]]]==NULL)
{
//dodaj wierz
pal_tree_node* pom= new pal_tree_node((najd->dlug)+2,(najd->hasz)*3+seq[konc[i]]+1);
najd->syn[seq[konc[i]]]=pom;
//znajdz pom->shrt
pal_tree_node* pom2=najd->shrt[seq[konc[i]]];
if(pom2==NULL)
pom2=jz[seq[konc[i]]];
else
pom2=pom2->syn[seq[konc[i]]];
//no i teraz musze wiedziec co jest po nim
int x=seq[konc[i-pom2->dlug]];
pom->shrt[x]=pom2;
pom2=pom2->shrt[1-x];
pom->shrt[1-x]=pom2;
}
najd=najd->syn[seq[konc[i]]];
if(mapy[a][najd->hasz]!=1)
{
mapy[a][najd->hasz]=1;
tusa[a].push_back(najd->hasz);
}
}
//sprawdz czy najd jest sufixem b
if(najd->dlug==i-po[a].first+1)
pref[a]=najd;
}
suf[a]=najd;
//DANGER!!!
po[a].second=po[b].second;
nal[b]=a;
for(auto i:tusa[b])
{
if(mapy[a][i]!=1)
{
mapy[a][i]=1;
tusa[a].push_back(i);
}
}
b=a;
}
cout<<tusa[a].size()<<'\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:77:27: warning: array subscript has type 'char' [-Wchar-subscripts]
77 | pref[i]=suf[i]=jz[wcz];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
8 ms |
3444 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1348 KB |
Output is correct |
| 17 |
Correct |
6 ms |
2388 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1748 KB |
Output is correct |
| 19 |
Correct |
32 ms |
12116 KB |
Output is correct |
| 20 |
Correct |
12 ms |
3924 KB |
Output is correct |
| 21 |
Correct |
65 ms |
22576 KB |
Output is correct |
| 22 |
Correct |
22 ms |
7036 KB |
Output is correct |
| 23 |
Correct |
1 ms |
596 KB |
Output is correct |
| 24 |
Correct |
1 ms |
596 KB |
Output is correct |
| 25 |
Correct |
1 ms |
852 KB |
Output is correct |
| 26 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
195812 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
212 KB |
Output is correct |
| 15 |
Correct |
8 ms |
3444 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1348 KB |
Output is correct |
| 17 |
Correct |
6 ms |
2388 KB |
Output is correct |
| 18 |
Correct |
5 ms |
1748 KB |
Output is correct |
| 19 |
Correct |
32 ms |
12116 KB |
Output is correct |
| 20 |
Correct |
12 ms |
3924 KB |
Output is correct |
| 21 |
Correct |
65 ms |
22576 KB |
Output is correct |
| 22 |
Correct |
22 ms |
7036 KB |
Output is correct |
| 23 |
Correct |
1 ms |
596 KB |
Output is correct |
| 24 |
Correct |
1 ms |
596 KB |
Output is correct |
| 25 |
Correct |
1 ms |
852 KB |
Output is correct |
| 26 |
Correct |
1 ms |
724 KB |
Output is correct |
| 27 |
Execution timed out |
1093 ms |
195812 KB |
Time limit exceeded |
| 28 |
Halted |
0 ms |
0 KB |
- |
