比赛 |
国庆欢乐赛3 |
评测结果 |
AAAAAAAAAATTTTT |
题目名称 |
Following Directions |
最终得分 |
67 |
用户昵称 |
wdsjl |
运行时间 |
16.950 s |
代码语言 |
C++ |
内存使用 |
110.13 MiB |
提交时间 |
2025-10-05 10:00:07 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1600;
vector<int> son[N*N+2*N];
int n,q,c[N*2],siz[N*N+2*N],f[N*N+2*N],ans;
char a[N][N];
int id(int x,int y){
if(x<=n&&y<=n){
return (x-1)*n+y;
}
if(x==n+1) {
return n*n+n+y;
}
return n*n+x;
}
void dfs(int x,int y,int fa){
int nid=id(x,y);
int nidx=id(x-1,y);
int nidy=id(x,y-1);
siz[nid]=1;
f[nid]=fa;
if(a[x][y-1]=='R'){
son[nid].push_back(nidy);
dfs(x,y-1,fa);
siz[nid]+=siz[nidy];
}
if(a[x-1][y]=='D'){
son[nid].push_back(nidx);
dfs(x-1,y,fa);
siz[nid]+=siz[nidx];
}
}
void dfs2(int x,int y,int fa,int cha){
ans+=cha;
f[id(x,y)]=fa;
if(a[x][y-1]=='R'){
dfs2(x,y-1,fa,cha);
}
if(a[x-1][y]=='D'){
dfs2(x-1,y,fa,cha);
}
}
signed main(){
freopen("zunxun.in","r",stdin);
freopen("zunxun.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
scanf("%lld",&c[i]);
}
for(int i=n+1;i<=2*n;i++){
scanf("%lld",&c[i]);
}
for(int i=1;i<=n;i++){
if(a[i][n]=='R'){
son[n*n+i].push_back(id(i,n));
dfs(i,n,i);
siz[n*n+i]=siz[id(i,n)];
}
}
for(int i=n+1;i<=2*n;i++){
if(a[n][i-n]=='D'){
son[n*n+i].push_back(id(n,i-n));
dfs(n,i-n,i);
siz[n*n+i]=siz[id(n,i-n)];
}
}
for(int i=1;i<=2*n;i++)ans+=c[i]*siz[n*n+i];
cout<<ans<<endl;
for(int i=1;i<=n;i++){
f[id(n+1,i)]=i+n;
f[id(i,n+1)]=i;
}
int q=0;
cin>>q;
while(q--){
int xx,yy;
cin>>xx>>yy;
int ff=0;
if(a[xx][yy]=='R') {
ff=f[id(xx+1,yy)];
a[xx][yy]='D';
}
else {
ff=f[id(xx,yy+1)];
a[xx][yy]='R';
}
int val=c[ff];
int cha=val-c[f[id(xx,yy)]];
dfs2(xx,yy,ff,cha);
cout<<ans<<endl;
}
return 0;
}