Educational Codeforces Round 53
Educational Codeforces Round 53
F. Choosing Two Paths(CF 1073F)
テーマの説明http://codeforces.com/contest/1073/problem/F
問題解は実は木の上で最も長い鎖のような方法で、根から下へ探して、もし1つの点が1人の子供より多いならば、それは起点とすることができます.各点の2人の最も深い子供を2つの起点として統計し、すべての合法的な点で問題の意味に合った最長チェーンを見つければいい.
コード
テーマの説明http://codeforces.com/contest/1073/problem/G
問題解lcpは接尾辞配列におけるheightの区間最小値である.だからこの考えに沿ってやればいい.a配列とb配列のすべての数字を接尾辞配列のrankに従って並べ替えて、左から右にスキャンして、単調なスタックを持って最小のheightとそれがカバーする区間を維持して、それから右から左にスキャンして同じことをすればいいです.コード能力が悪すぎて、これは長い間書いていました...
コード
F. Choosing Two Paths(CF 1073F)
テーマの説明http://codeforces.com/contest/1073/problem/F
問題解は実は木の上で最も長い鎖のような方法で、根から下へ探して、もし1つの点が1人の子供より多いならば、それは起点とすることができます.各点の2人の最も深い子供を2つの起点として統計し、すべての合法的な点で問題の意味に合った最長チェーンを見つければいい.
コード
#include
#define N 200010
using namespace std;
int n,A,B,C,D,pos,dep[N],f[N],g[N];
int k,la[N],ff[N*2];
struct info{
int x,y;
bool operatordep[f[x]])g[x]=f[x],f[x]=f[e[a].b];
else if(dep[f[e[a].b]]>dep[g[x]])g[x]=f[e[a].b];
}
if(!cnt)f[x]=x;
if(cnt>=2)
{
info tmp=(info){dep[x],dep[f[x]]+dep[g[x]]-dep[x]*2};
if(res
G. Yet Another LCP Problem(CF 1073G) テーマの説明http://codeforces.com/contest/1073/problem/G
問題解lcpは接尾辞配列におけるheightの区間最小値である.だからこの考えに沿ってやればいい.a配列とb配列のすべての数字を接尾辞配列のrankに従って並べ替えて、左から右にスキャンして、単調なスタックを持って最小のheightとそれがカバーする区間を維持して、それから右から左にスキャンして同じことをすればいいです.コード能力が悪すぎて、これは長い間書いていました...
コード
#include
#define N 200010
#define ll long long
using namespace std;
int n,m,Q,a[N],b[N],q[N],p[N];char s[N];ll ans;
int cnt[N],x[N],y[N],t[N],sa[N],g[N][20],rk[N],height[N];
struct info{
int x,tp,k;
bool operatorp.tp);
return rk[x]>rk[p.x]||(x==p.x&&tpj)y[++tot]=sa[i]-j;
for(int i=1;i<=n;i++)t[i]=x[y[i]];
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)cnt[t[i]]++;
for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
for(int i=n;i;i--)sa[cnt[t[i]]--]=y[i];
tot=2;swap(x,y);x[sa[1]]=1;
for(int i=2;i<=n;i++)
x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?tot-1:tot++;
}
}
void get_height()
{
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1,j,k=0;i<=n;height[rk[i++]]=k)
for(k=k?k-1:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
}
void get_rmq()
{
memset(g,127,sizeof(g));
for(int i=1;i<=n;i++)g[i][0]=height[i];
for(int j=1;(1<y)swap(x,y);x++;
int p=log2(y-x+1);
return min(g[x][p],g[y-(1<