关于USACO
  • 板块学术版
  • 楼主yujinning
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/2/9 09:31
  • 上次更新2023/10/24 01:21:12
查看原帖
关于USACO
601224
yujinning楼主2023/2/9 09:31

USACO赛时AC的代码为何赛后提交就无法通过?

Ag-T2.

赛时AC: logo

赛后重测: logo

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1509;
ll n,Q,p[N*2],sz[N*N+2*N],f[N*N+2*N],ans;
char a[N][N];
vector<ll> son[N*N+2*N];
inline ll id(ll x,ll y){
	if(x<=n&&y<=n) return (x-1)*n+y;
	if(x==n+1) return n*n+n+y;
	return n*n+x;
}
inline void dfs(ll x,ll y,ll fa){
	ll ider=id(x,y),iderx=id(x-1,y),idery=id(x,y-1);
	sz[ider]=1;
	f[ider]=fa;
	if(a[x][y-1]=='R'){
		son[ider].push_back(idery);
		dfs(x,y-1,fa);
		sz[ider]+=sz[idery];
	}
	if(a[x-1][y]=='D'){
		son[ider].push_back(iderx);
		dfs(x-1,y,fa);
		sz[ider]+=sz[iderx];
	}
}
inline void dfs_bao(ll x,ll y,ll fa,ll cha){
    ans+=cha;
    f[id(x,y)]=fa;
    if(a[x][y-1]=='R')
		dfs_bao(x,y-1,fa,cha);
	if(a[x-1][y]=='D')
		dfs_bao(x-1,y,fa,cha);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(register ll i=1;i<=n;i++){
		for(register ll j=1;j<=n;j++) cin>>a[i][j];
		cin>>p[i];
	}
	for(register ll i=n+1;i<=2*n;i++) cin>>p[i];
	for(register ll i=1;i<=n;i++){
		if(a[i][n]=='R'){
		    son[n*n+i].push_back(id(i,n));
			dfs(i,n,i);
			sz[n*n+i]=sz[id(i,n)];
		}
	}
	for(register ll 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);
			sz[n*n+i]=sz[id(n,i-n)];
		}
	}
	for(register ll i=1;i<=2*n;i++)
		ans+=p[i]*sz[n*n+i];
	cout<<ans<<endl;
	for(register ll i=1;i<=n;i++){
		f[id(n+1,i)]=i+n;
		f[id(i,n+1)]=i;
	}
	int q=0;
	cin>>Q; q=Q;
	while(Q--){
		ll opx,opy;
		cin>>opx>>opy;
		ll faxyer=0;
		if(a[opx][opy]=='R') faxyer=f[id(opx+1,opy)],a[opx][opy]='D';
		else faxyer=f[id(opx,opy+1)],a[opx][opy]='R';
		ll val=p[faxyer];
		ll cha=val-p[f[id(opx,opy)]];
		dfs_bao(opx,opy,faxyer,cha);
		cout<<ans<<endl;
	}
	return 0;
}
'''
2023/2/9 09:31
加载中...