比赛 国庆欢乐赛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;
}