XIV Open Cup named after E.V. Pankratiev. GP of Udmurtia.

(正しい名称がわからないのでタイトル丸コピペしました。)

JAPLJさん, rng_58さんと参加。6完8位でした。二人ともプロ過ぎて怖い。
自分が解いた問題だけ貼っておきます

J:
やるだけ。というより英語を読むだけ。ただし英語が読めず嵌る。りんごさんに英語を読んでもらいすぐ直る。こういうの困る。

#include<stdio.h>
#include<algorithm>
using namespace std;
int UF[2000000];
int c[2000][2000];
pair<int,pair<int,int> > edge[3000000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);
	if(a==b)return;
	UF[a]+=UF[b];
	UF[b]=a;
	return;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			scanf("%d",&c[i][j]);
	int now=0;
	int val=1999999999;
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			val=min(val,c[i][j]);
	if(a==1){
		int ret=1999999999;
		for(int i=0;i<b;i++)ret=min(ret,c[0][i]);
		printf("%d\n",ret-val+1);
		return 0;
	}
	for(int i=0;i<a*b+2;i++)UF[i]=-1;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(i<a-1){
				edge[now++]=make_pair(max(c[i][j],c[i+1][j]),make_pair(i*b+j,i*b+b+j));
			}
			if(j<b-1){
				edge[now++]=make_pair(max(c[i][j],c[i][j+1]),make_pair(i*b+j,i*b+1+j));
			}
		}
	}
	std::sort(edge,edge+now);
	for(int i=0;i<b;i++){
		UNION(a*b,i);
		UNION(a*b+1,(a-1)*b+i);
	}
	//for(int i=0;i<b-1;i++){UNION(i,i+1);UNION((a-1)*b+i,(a-1)*b+i+1);}
	for(int i=0;i<now;i++){
		UNION(edge[i].second.first,edge[i].second.second);
		if(FIND(a*b)==FIND(a*b+1)){
			printf("%d\n",edge[i].first-val+1);
			return 0;
		}
	}
}

サンプル両方に高さ1が含まれているせいで問題文が読めないと永遠に嵌ることになります。

I:
解法：まずは与えられる文字列とクエリの文字列全部まとめてAho-Corasick木をつくる。各頂点で「そこ以下での文字列の終わりだよマークの数」を持っておく。Failure Link上でDFSして「Failure Linkにおけるそこ以下での「そこ以下での文字列の終わりだよマークの数」」の総計がその頂点に対応する文字列が含まれる回数。
2年ぶりにAho-Corasick書いたけど普通にあっさりかけた。2000010を5000000にしててMLEが1つ。

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
struct Trie{
	int rev;
	int fail;
	int child[26];
	int x;
	int mark;
	Trie(){
		fail=0;
		rev=-1;
		mark=0;
		x=0;
		for(int i=0;i<26;i++){
			child[i]=-1;
		}
	}
};
vector<int> v[2000010];
Trie p[2000010];
int siz=1;
char in[1100000];
int conv[1100000];
int sum[2000010];
long long ans[2000010];
int dfs1(int a){
	int ret=p[a].mark;
	for(int i=0;i<26;i++){
		if(~p[a].child[i]){
			ret+=dfs1(p[a].child[i]);
		}
	}
	sum[a]=ret;
	return ret;
}
long long dfs2(int a){
	long long ret=sum[a];
	for(int i=0;i<v[a].size();i++)ret+=dfs2(v[a][i]);
	ans[a]=ret;
	return ret;
}
int main(){

	int a;
	scanf("%d",&a);
	p[0].rev=-1;

	for(int i=0;i<a;i++){
		int x,y;
		scanf("%d%s%d",&x,in,&y);
		p[x].child[in[0]-'a']=i+1;
		p[i+1].rev=x;
		p[i+1].mark=y;
		p[i+1].x=in[0]-'a';
	}
	siz=a+1;
	int b;
	scanf("%d",&b);
	for(int i=0;i<b;i++){
		scanf("%s",in);
		int len=strlen(in);
		int at=0;
		for(int j=0;j<len;j++){
			if(p[at].child[in[j]-'a']==-1){
				p[at].child[in[j]-'a']=siz;
				p[siz].rev=at;
				p[siz].x=in[j]-'a';
				at=siz;
				siz++;
			}else{
				at=p[at].child[in[j]-'a'];
			}
		}
		conv[i]=at;
	}
	
	dfs1(0);
	queue<int> Q;
	
	Q.push(0);
	while(Q.size()){
		int at=Q.front();
		Q.pop();
		for(int i=0;i<26;i++){
			if(~p[at].child[i]){
				Q.push(p[at].child[i]);
			}
		}
		if(at==0)continue;
		int now=p[at].rev;
		if(now==0){
			p[at].fail=0;
			continue;
		}
		while(1){
			now=p[now].fail;
			if(~p[now].child[p[at].x]){
				p[at].fail=p[now].child[p[at].x];
				break;
			}else if(now==0){
				p[at].fail=0;
				break;
			}
		}
	}
//	for(int i=0;i<siz;i++)printf("%d %c %d\n",p[i].rev,'a'+p[i].x,p[i].fail);
	for(int i=1;i<siz;i++){
		v[p[i].fail].push_back(i);
	}
	dfs2(0);
	for(int i=0;i<b;i++)printf("%lld\n",ans[conv[i]]);
}

B:　データが間違ってたらしい
D:　これは絶対つらい
F:　人間がとくものではない
G:　バケット法だと無理っぽい
H:　は？？？