2022牛客暑期多校训练营3 个人题解

---

title :2022牛客暑期多校训练营3 题解
date : 2022-8-16
tags : ACM,练习记录
author : Linno

---

2022牛客暑期多校训练营3 题解

题目链接 ：https://ac.nowcoder.com/acm/contest/33188

补题进度 ：8/10

A - Ancestor

方法1：LCA是可以合并的，因此我们对于去掉特定一个关键点的LCA，只需要把前缀LCA和后缀LCA合并即可。

方法2：我们把所有关键点的LCA记下来，询问时能改变它的情况非常少，分类讨论有：①如果该点是全局LCA，那么只需要O(n)求一次这种情况；②如果子树下不存在关键点并且全局LCA的分支只有两个时，O(n)跑一边LCA；③其他情况下不影响全局LCA。

方法3：从方法2的分类讨论也可以得出来，其实全局LCA就是dfs序最大和最小的两个点的LCA，因此如果删的点并不是其中任何一个，就不会造成影响。

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+7;
const int mod=1e9+7;

int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
int n,k,x[N],is[N];

struct Tree{
	int val[N],dep[N],fa[N],sz[N],siz[N],son[N],top[N],suf[N],pre[N];
	vector<int>G[N];
	inline void dfs1(int x){
		if(is[x]) sz[x]=1;
		siz[x]=1;
		for(auto to:G[x]){
			if(to==fa[x]) continue;
			fa[to]=x;
			dep[to]=dep[x]+1;
			dfs1(to);
			sz[x]+=sz[to];
			siz[x]+=siz[to]; 
			if(sz[son[x]]<sz[to]) son[x]=to;
		}
	}
	inline void dfs2(int x,int tp){
		top[x]=tp;
		if(son[x]) dfs2(son[x],tp);
		for(auto to:G[x]){
			if(to!=fa[x]&&to!=son[x]) dfs2(to,to);
		}
	}
	inline int LCA(int x,int y){
		while(top[x]!=top[y]){
			if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
			else y=fa[top[y]];
		}
		return dep[x]<dep[y]?x:y;
	}
	inline void init(){
		for(int i=1;i<=n;++i) sz[i]=fa[i]=dep[i]=suf[i]=pre[i]=0;
		dfs1(1);
		dfs2(1,1);
		pre[1]=x[1],suf[k]=x[k];
		for(int i=2;i<=k;++i){
			pre[i]=LCA(pre[i-1],x[i]);
//			cout<
		}
		for(int i=k-1;i>=1;--i){
			suf[i]=LCA(suf[i+1],x[i]);
//			cout<
		}
	}
}A,B;


void Solve(){
	n=read();
	k=read();
	for(int i=1;i<=k;++i){
		x[i]=read();
		is[x[i]]=1;
	}
	for(int i=1;i<=n;++i) A.val[i]=read();
	for(int i=2,y;i<=n;++i){
		y=read();
		A.G[i].emplace_back(y);
		A.G[y].emplace_back(i);
	}
	for(int i=1;i<=n;++i) B.val[i]=read();
	for(int i=2,y;i<=n;++i){
		y=read();
		B.G[i].emplace_back(y);
		B.G[y].emplace_back(i);
	}
	A.init();B.init();
	int ans=0;
	if(A.val[A.suf[2]]>B.val[B.suf[2]]) ++ans;
	if(A.val[A.pre[k-1]]>B.val[B.pre[k-1]]) ++ans;
	for(int i=2;i<k;++i){
		if(A.val[A.LCA(A.pre[i-1],A.suf[i+1])]>B.val[B.LCA(B.pre[i-1],B.suf[i+1])]){
			++ans;
		}
	}
	write(ans);putchar('\n');
}

signed main(){
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

B - Boss

模拟费用流，讨论区的walkalone那篇题解写得很好，水平有限就不做补充了，这里引用一下。

#include
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
using pii = pair<ll,int>;
priority_queue<pii,vector<pii>,greater<pii>>q[15][15];
 
int n,k;
 
signed main(){
    scanf("%d%d",&n,&k);
    vector<int>now(n+1,1),e(k+1); //now[i]表示第i个人目前工作的城市
    for(int i=1;i<=k;++i) scanf("%d",&e[i]);
    vector<vector<ll>>c(n+1,vector<ll>(k+1));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=k;++j){
            scanf("%lld",&c[i][j]);
        }
    } 
    ll ans=0;
    for(int i=1;i<=n;++i){
        ans+=c[i][1];
        for(int j=2;j<=k;++j){
            q[1][j].emplace(c[i][j]-c[i][1],i);
        }
    }
    queue<int>que;
    for(int i=2;i<=k;++i){
        for(int times=1;times<=e[i];++times){
            vector<ll>dis(k+1,inf);
            que.emplace(1);
            vector<int>pre(k+1,0),vis(k+1,0);
            vis[1]=1;dis[1]=0;
            while(que.size()){
                int fro=que.front();
                que.pop();
                vis[fro]=0;
                for(int j=2;j<=k;++j){
                    while(q[fro][j].size()&&now[q[fro][j].top().second]!=fro){
                        q[fro][j].pop();//当前人已经不在tp城市工作了，因而这条边废弃
                    }
                    if(q[fro][j].size()&&dis[j]>dis[fro]+q[fro][j].top().first){
                        dis[j]=dis[fro]+q[fro][j].top().first;
                        pre[j]=fro;
                        if(!vis[j]){
                            vis[j]=1;
                            que.emplace(j);
                        }
                    }
                }
            }
            ans+=dis[i];
            int place=i;
            while(place!=1){
                int fa=pre[place];
                int ori_id=q[fa][place].top().second;
                now[ori_id]=place;  //退流表现为人工作城市的变化
                for(int i=1;i<=k;++i){
                    if(i!=place) q[place][i].emplace(c[ori_id][i]-c[ori_id][place],ori_id);
                }
                place=fa;
            }
        }
    }
    printf("%lld\n",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

C - Concatenation

很无语一道题，一开始写Trie写了巨久，结果stable_sort()过了。

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
using namespace std;
const int mod=1e9+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
//void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}

int n;
string s;
vector<string>str;

bool cmp(string A,string B){
	return A+B<B+A;
}

void Solve(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>s;
		str.emplace_back(s);
	}
	stable_sort(str.begin(),str.end(),cmp);
	for(int i=0;i<n;++i){
		cout<<str[i];
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);
//  freopen("out.cpp","w",stdout);
	int T=1;
//	cin>>T;
//	clock_t start,finish;
//	start=clock();
	while(T--){
		Solve();
	}
//	finish=clock();
//	cerr<<((double)finish-start)/CLOCKS_PER_SEC<
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

D - Directed

一个有用的结论就是如果不考虑单向边，x到父亲的期望步数是$2\ast sz[i]-1$。

考虑x向父亲f建单向边时，对于x是没有影响的，而f期望步数要减去x子树大小。

式子不会推，大概就是差分统计一下s到树根每个点的影响，然后分类讨论一下就行了。

#include
#define int long long
using namespace std;

const int N=1e6+7;
const int mod=998244353;

int n,k,s,frac[N],ifrac[N];
vector<int>G[N];

int fpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

int sz[N],fa[N],dep[N],c[N];
void dfs1(int x,int f){
	fa[x]=f;
	for(auto to:G[x]){
		if(to==f) continue;
		dep[to]=dep[x]+1;
		dfs1(to,x);
	}
}

void dfs2(int x){
	for(auto to:G[x]){
		if(to==fa[x]) continue;
		sz[to]+=sz[x];
		dfs2(to);
	}
}

inline int C(int n,int m){
	if(n<m) return 0;
	return frac[n]*ifrac[m]%mod*ifrac[n-m]%mod;
}

signed main(){
	cin>>n>>k>>s;
	frac[0]=1;for(int i=1;i<=n;++i) frac[i]=frac[i-1]*i%mod;
	ifrac[n]=fpow(frac[n],mod-2);
	for(int i=n;i>=1;--i) ifrac[i-1]=ifrac[i]*i%mod;
	for(int i=1,u,v;i<n;++i){
		cin>>u>>v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	dfs1(1,0);
	for(int i=s;i!=1;i=fa[i]) sz[i]=1;
	dfs2(1);
	for(int i=2;i<=n;++i){
		c[dep[i]-sz[i]]++;
		c[dep[i]]--;
	}
	for(int i=1;i<n;++i) c[i]+=c[i-1];
	int ans=0;
	for(int i=1;i<=n-k;++i){
		ans=(ans+c[i-1]*C(n-i,k)%mod+mod)%mod;
	}
	ans*=ifrac[n-1]*frac[k]%mod*frac[n-1-k]%mod;
	ans%=mod;
	ans=(2ll*ans-dep[s])%mod;
	cout<<ans<<"\n";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

E - Electrician

没补

F - Fief

对于一条链，我们左右两端都得是固定的，也就是询问的两个点必须是两端的点才行；

对于一个环来说肯定是满足的，可以从任意地方进入任意地方退出；

对于一棵树肯定不满足，因为没办法回退到第三个分支。

那么步骤就是：①特判两个点满足；②tarjan求点双，且判掉两个以上连通块不满足；③重建图后判树；④判是否为链的两端

#include
using namespace std;
const int N=1e6+7;

int n,m,q,rt,deg[N],is[N],sccnum=0;

struct E{
	int u,v,nxt;
}e[N<<2];
int cnt=0,head[N];
inline void addedge(int u,int v){e[++cnt]=(E){u,v,head[u]};head[u]=cnt;}
vector<int>dcc[N]; 
int dcnt=0; 

int dfn[N],low[N],idx=0,stk[N],top=0,vis[N],bel[N];
void tarjan(int x,int in){
	dfn[x]=low[x]=++idx;
	stk[++top]=x;
	if(x==rt&&!head[x]){
		dcc[++dcnt].emplace_back(x);
		return;
	} 
	int col=0;
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].v;
		if(!dfn[to]){
			tarjan(to,i);
			low[x]=min(low[x],low[to]);
			if(dfn[x]<=low[to]){
				++col;
				if(x!=rt||col>1) is[x]=1;
				dcnt++;
				int y;
				do{
					y=stk[top--];
					dcc[dcnt].emplace_back(y);
				}while(y!=to);
				dcc[dcnt].emplace_back(x);
			}
		}else low[x]=min(low[x],dfn[to]);
	}
}

void sayyes(){for(int i=1,u,v;i<=q;++i){cin>>u>>v;cout<<"YES\n";}}
void sayno(){for(int i=1,u,v;i<=q;++i){cin>>u>>v;cout<<"NO\n";}}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;++i){
		cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	cin>>q;	
	if(n==2){sayyes();return 0;}
	int ltk=0,st=0,ed=0;
	for(int i=1;i<=n;++i){  //缩点 
		if(!dfn[i]){
			++ltk;
			rt=i;
			tarjan(i,0);
		}
	}
	if(ltk>=2){sayno();return 0;}
	sccnum=dcnt;
	for(int i=1;i<=n;++i) if(is[i]) bel[i]=++sccnum;
	for(int i=1;i<=dcnt;++i){
		for(int j=0;j<dcc[i].size();++j){
			int v=dcc[i][j];
			if(is[v]) deg[i]++,deg[bel[v]]++;
			else bel[v]=i;
		}
	}
	for(int i=1;i<=sccnum;++i) if(deg[i]>2){sayno();return 0;}
	for(int i=1,u,v;i<=q;++i){
		cin>>u>>v;
		int fx=bel[u],fy=bel[v];  //需要是链的两端才行
		if(!deg[fx]&&!deg[fy]) cout<<"YES\n";
		else if(deg[fx]==1&&deg[fy]==1&&fx!=fy) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

G - Geometry

求两个凸包的相撞时间。实际上就是求它们的闵可夫斯基和与原点沿运动合成方向的射线相交的时间，全是套板子。特判掉0的情况（原点在凸包里）以及-1的情况（不动或者不与凸包相交）

#include
#define Vector Point
//#define inf 0x7f7f7f7f
//#define int long long
#define db long double
using namespace std;
typedef long long ll;
//const int N=1e5+7;
const db eps=1e-10,pi=acos(-1.0);
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

//inline int dcmp(db a){return a<-eps?-1:(a>eps?1:0);}  //处理精度 
//inline db Abs(db a){return a*dcmp(a);} //取绝对值 

struct Point{
    db x,y;
    Point(){ SetZero(); }
    Point(db _x,db _y){ Set(_x,_y); }
    inline void Set(db _x,db _y){ x=_x,y=_y; }
    inline void SetZero(){ x=y=0; }
    inline Point operator +(const Point &v) const{ return Point(x+v.x,y+v.y); }
    inline Point operator +=(const Point &v){ return *this=*this+v; }
    inline Point operator -() const{ return Point(-x,-y); }
    inline Point operator -(const Point &v) const{ return Point(x-v.x,y-v.y); }
    inline Point operator -=(const Point &v){ return *this=*this-v; }
    inline Point operator *(db f) const{ return Point(f*x,f*y); }
    inline friend Point operator *(db f,const Point &v){ return v*f; }
    inline Point operator *=(db f){ return *this=*this*f; }
    inline Point operator /(db f) const{ return *this*(1.0/f); }
    inline Point operator /=(db f){ return *this=*this/f; }
 
    inline bool operator <(const Point &b){
        auto up=[](const Point &a){
            if(a.IsZero()) return -1;
            return int(a.y>eps||(a.y>-eps&&a.x>-eps));
        };
        int qa=up(*this),qb=up(b);
        if(qa!=qb) return qa>qb;
        return Cross(*this,b)>eps;
    }
    inline bool IsZero() const{ return abs(x)<=eps&&abs(y)<=eps; }
    inline bool operator ==(const Point &v) const{ return (*this-v).IsZero(); }
    inline friend db Cross(const Point &p,const Point &q){ return p.x*q.y-p.y*q.x; }
    inline friend db Dot(const Point &p,const Point &q){ return p.x*q.x+p.y*q.y; }
    inline Point Rot90() const{ return Point(-y,x); }
    inline Point Rot90CW() const{ return Point(y,-x); }
    inline db SqrLen() const{ return x*x+y*y; }
    inline db Length() const{ return sqrt(x*x+y*y); }
    inline Point Normalized() const{
        db len=Length();
        if(len<=eps) return Point(0,0);
        db invLen=1.0/len;
        return Point(x*invLen,y*invLen);
    }
    inline Point Normalize(){ return *this=this->Normalized(); }
    inline db Arg() const{ return atan2(y,x); }
    inline friend istream &operator >>(istream &is,Point &v){ return is>>v.x>>v.y; }
    inline friend ostream &operator <<(ostream &os,const Point &v){
        os<<setiosflags(ios::fixed)<<setprecision(6);
        os<<"("<<setw(9)<<v.x<<','<<setw(9)<<v.y<<")";
        return os<<setprecision(6)<<resetiosflags(ios::fixed);
    }
};

struct Line{
    int u,v;
    Point ori,dir;
    Line(){ SetZero(); }
    Line(const Point &_ori,const Point &_dir){ Set(_ori,_dir); }
    inline void Set(const Point &_ori,const Point &_dir){
        ori=_ori,dir=_dir.Normalized();
    }
    inline void SetdbwoPoints(const Point &p1,const Point &p2){ Set(p1,p2-p1); }
    inline void SetZero(){ ori.SetZero(),dir.Set(1,0); }
    inline bool OnLeft(const Point &p){
        return Cross(dir,p-ori)>0;
    }
    inline db Arg() const{ return dir.Arg(); }
    inline friend Point Intersect(const Line &lA,const Line &lB){
        db k=Cross(lB.ori-lA.ori,lB.dir)/Cross(lA.dir,lB.dir);
        return lA.ori+lA.dir*k;
    }
};
 

vector<Point> minksum(vector<Point> &a,vector<Point> &b){
    int n=a.size(),m=b.size();
    vector<Point> ret(n+m+1);
    auto cmp=[](Point l,Point r){ return l.y<r.y||(l.y==r.y&&l.x<r.x); };
    rotate(a.begin(),min_element(a.begin(),a.end(),cmp),a.end());
    rotate(b.begin(),min_element(b.begin(),b.end(),cmp),b.end());
    ret[0]=a[0]+b[0];
    vector<Point> qa(n),qb(m);
    for(int i=0;i<n;++i) qa[i]=a[(i+1)%n]-a[i];
    for(int i=0;i<m;++i) qb[i]=b[(i+1)%m]-b[i];
    merge(qa.begin(),qa.end(),qb.begin(),qb.end(),ret.begin()+1);
    for(int i=1;i<=n+m;++i) ret[i]+=ret[i-1];
    return ret;
}
 

bool InPoly(const vector<Point> &ps,Point p){  //是否在凸包里边 
	int n=ps.size();
	if(n<3) return 0;
	for(int i=0;i<n;++i){
		if(Cross(ps[i]-p,ps[(i+1)%n]-p)<-eps) return 0;
	}
	return 1;
} 

signed main(){
    int n=read();
    vector<Point> A(n);
    for(auto &p:A) p.x=read(),p.y=read();
    int m=read();
    vector<Point> B(m);
    for(auto &p:B) p.x=-read(),p.y=-read();
    Point v;
    v.x=-read(),v.y=-read();
    v.x+=read(),v.y+=read();
    auto H=minksum(A,B);
    if(InPoly(H,Point())) return puts("0"),0;
    if(v.IsZero()) return puts("-1"),0;
    int N=H.size();
    db ans=1e19;
	for(int i=0;i<N;++i){
        Point p=H[i],q=H[(i+1)%N];
        Line l(Point(),v);
        if(Cross(q,v)*Cross(p,v)<=eps){
            auto s=Intersect(l,Line(p,q-p));
            if(Dot(s,v)<-eps) continue;
         	ans=min(ans,s.Length()/v.Length());
        }
    }
    if(ans>1e18) puts("-1");
    else printf("%.10Lf",ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

H - Hacker

建一棵SAM，然后把每个串放进去跑，就能得到可以取值的一些范围，将这些范围用线段树合并然后询问最大值即可。

#include
#define inf 1e18
typedef long long ll;
using namespace std;
const int N=1e6+7;

char s[N];
int n,m,k;
ll w[N];

namespace SAM{
	const int MAXLEN=2e6+2;
	int SZ=1,lst=1;  //当前自动机大小和整个字符串最后状态 
	
	struct edge{int v,nxt;}e[MAXLEN<<1];
	int head[MAXLEN],cnt=0;
	void add(int u,int v){e[++cnt]=(edge){v,head[u]};head[u]=cnt;}
	
	struct state{   //SAM上的信息结点 
		int len,fa,sz;   //长度和后缀链接
		//mapch;
		int ch[26];  //转移列表 
	}st[MAXLEN];  //最多2*n-1个状态 
	void clr(int size){
		SZ=lst=1;cnt=0;
		for(int i=0;i<=size;++i){
			head[i]=0;
			st[i].len=st[i].fa=st[i].sz=0;
			memset(st[i].ch,0,sizeof(st[i].ch));
		}
	}
	void ins(int c){ //添加字符 
		int p=lst,np=lst=++SZ;   //创建新的状态结点 
		st[np].sz=1;
		st[np].len=st[p].len+1;
		for(;p&&!st[p].ch[c];p=st[p].fa) st[p].ch[c]=np;
		if(!p) st[np].fa=1;
		else{
			int q=st[p].ch[c];
			if(st[q].len==st[p].len+1) st[np].fa=q;
			else{
				int nq=++SZ;
				st[nq]=st[q];st[nq].len=st[p].len+1;
				st[q].fa=st[np].fa=nq;
				st[nq].sz=0;
				for(;p&&st[p].ch[c]==q;p=st[p].fa) st[p].ch[c]=nq;
			}
		}
	}
};
using namespace SAM;

#define ls (p<<1)
#define rs (p<<1|1)
struct Tree{
	int l,r;
	ll lmx,rmx,sum,mx;
}tr[N<<2];
Tree pushup(Tree A,Tree B){
	Tree res;
	res.l=A.l;res.r=B.r;
	res.lmx=max(A.lmx,A.sum+B.lmx);
	res.rmx=max(B.rmx,A.rmx+B.sum);
	res.mx=max(A.rmx+B.lmx,max(A.mx,B.mx));
	res.sum=A.sum+B.sum;
	return res; 
}

void build(int p,int l,int r){
	tr[p].l=l;tr[p].r=r;
	if(l==r){
		tr[p].sum=tr[p].lmx=tr[p].rmx=tr[p].mx=w[l];
		return;
	}
	int mid=((l+r)>>1);
	build(ls,l,mid);
	build(rs,mid+1,r);
	tr[p]=pushup(tr[ls],tr[rs]);
}

Tree query(int p,int ql,int qr){
	if(ql<=tr[p].l&&tr[p].r<=qr) return tr[p];
	int mid=((tr[p].l+tr[p].r)>>1);
	if(ql>mid) return query(rs,ql,qr);
	else if(qr<=mid) return query(ls,ql,qr);
	else{
		Tree res,L,R;
		L=query(ls,ql,qr);
		R=query(rs,ql,qr);
		res=pushup(L,R);
		return pushup(L,R);
	}
}

signed main(){
	scanf("%d%d%d",&n,&m,&k); 
	scanf("%s",s);
	for(int i=0;i<n;++i) ins(s[i]-'a');
	//for(int i=1;i<=SZ;++i) add(st[i].fa,i);
	for(int i=1;i<=m;++i) scanf("%lld",&w[i]);
	build(1,1,m); 
	for(int i=0;i<k;++i){
		scanf("%s",s);
		int p=1,t=0,len=strlen(s);
		ll res=-inf;
		for(int j=0,sta,ed;j<len;++j){
			int c=s[j]-'a';
			while(p>1&&!st[p].ch[c]){
				p=st[p].fa;
				t=st[p].len;
			}
			ed=j;
			if(st[p].ch[c]){
				p=st[p].ch[c];
				++t;
				++ed;
			}
			if(t){
				sta=ed-t+1;
				res=max(0ll,max(res,query(1,sta,ed).mx));
			}
		}
		printf("%lld\n",res);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

I - Ice Drinking

没补

J - Journey

建一个图，与右边的点连边时费用为0，跑最短路即可，用(s,t)来表示每个点方便更新答答案。

//#pragma GCC optimize("Ofast", "inline", "-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e5+7;

struct nod{
	int u,v,s;
	bool operator <(nod B)const{
		return s>B.s;
	}
};

#define mk make_pair
#define pii pair<int,int>
map<pii,int>vis;

int n,ans=inf,s1,s2,t1,t2,c[N][5];

int get_dir(int a,int b){
	for(int i=0;i<4;++i) if(c[b][i]==a) return (i+1)%4;
	return -1;
}

int bfs(){
	priority_queue<nod>q;
	q.push((nod){s1,s2,0});
	while(q.size()){
		nod fro=q.top();
		q.pop();
		//cout<
		if(fro.u==t1&&fro.v==t2) return fro.s;
		int dir=get_dir(fro.u,fro.v);
		for(int i=0;i<4;++i){
			int j=c[fro.v][i];
			if(j==0) continue;
			int v=(i==dir)?0:1;
			if(!vis.count(mk(fro.v,j))||vis[mk(fro.v,j)]>fro.s+v){
				vis[mk(fro.v,j)]=fro.s+v;
				q.emplace((nod){fro.v,j,vis[mk(fro.v,j)]});
			}
		}
	}
	return -1;
}

signed main(){
	scanf("%d",&n); 
	for(int i=1;i<=n;++i){
		for(int j=0;j<4;++j) scanf("%d",&c[i][j]);
	}
	scanf("%d%d%d%d",&s1,&s2,&t1,&t2);
	printf("%d\n",bfs());
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56