QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54569#4231. Rafting TripYL1F4#WA 10ms34804kbC++144.2kb2022-10-09 18:30:452022-10-09 18:30:47

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-09 18:30:47]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:34804kb
  • [2022-10-09 18:30:45]
  • 提交

answer

#include<cstdio>
#include<set>
#include<utility>
#include<queue>
const int maxn=505;
char s[maxn][maxn];
int n,m;
std::set<std::pair<int,int>>qs[maxn][maxn];
std::multiset<std::pair<int,int>>qsm[maxn][maxn];
std::pair<int,int>add(std::pair<int,int>a,std::pair<int,int>b){
	return std::make_pair(a.first+b.first,a.second+b.second);
}
std::pair<int,int>dir(char c){
	if(c=='<'){
		return {0,-1};
	}else if(c=='>'){
		return {0,1};
	}else if(c=='v'){
		return {1,0};
	}else if(c=='^'){
		return {-1,0};
	}
	return {0,0};
}
std::pair<int,int>dir(std::pair<int,int>p){
	return dir(s[p.first][p.second]);
}
bool chkin(std::pair<int,int>p){
	return (p.first>0&&p.first<=n)&&(p.second>0&&p.second<=m);
}
namespace top{
	std::queue<std::pair<int,int>>q;
	int deg[maxn][maxn];
	bool vis[maxn][maxn];
	void tps(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				std::pair<int,int>tmp=add(dir(s[i][j]),{i,j});
				deg[tmp.first][tmp.second]++;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(!deg[i][j]){
					q.push({i,j});
				}
			}
		}
		while(q.size()){
			auto u=q.front();q.pop();
			vis[u.first][u.second]=1;
			if(chkin(add(u,dir(u)))){
				auto v=add(u,dir(u));
				deg[v.first][v.second]--;
				if(deg[v.first][v.second]==0){
					q.push(v);
				}
			}
		}
	}
}
namespace merge{
	std::pair<int,int>fa[maxn][maxn];
	bool vis[maxn][maxn];
	void dfs(std::pair<int,int>u,std::pair<int,int>sr){
//		printf("%d %d %d %d\n",u.first,u.second,sr.first,sr.second);
		std::pair<int,int>v=add(u,dir(u));
		vis[u.first][u.second]=1;
		fa[u.first][u.second]=sr;
		if(vis[v.first][v.second]){
			return;
		}
		dfs(v,sr);
		for(auto c: "<>^v"){
			v=add(u,dir(c));
			if(s[v.first][v.second]=='#'){
				qs[sr.first][sr.second].insert(v);
				qsm[sr.first][sr.second].insert(v);
			}
		}
	}
	void init(){
		top::tps();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(!top::vis[i][j]&&!vis[i][j]&&dir(s[i][j])!=std::pair<int,int>{0,0}){
					dfs({i,j},{i,j});
				}else if(!vis[i][j]){
					fa[i][j]=std::pair<int,int>{i,j};
				}
			}
		}
	}
}
int ans=0;
namespace top2{
	std::vector<std::pair<int,int>>g[maxn][maxn];
	int deg[maxn][maxn];
	void build(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(merge::vis[i][j]){
					continue;
				}
				if(dir({i,j})==std::pair<int,int>{0,0}){
					continue;
				}
				std::pair<int,int>v={i,j};
				v=add(v,dir(v));
				if(dir(v)==std::pair<int,int>{0,0}){
					continue;
				}
				if(chkin(v)){
					v=merge::fa[v.first][v.second];
					g[v.first][v.second].push_back({i,j});
					deg[i][j]++;
				}
			}
		}
//		puts("deg");
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
//				printf("%d ",deg[i][j]);
//			}puts("");
//		}
	}
	std::set<std::pair<int,int>>tmp;
	std::multiset<std::pair<int,int>>tmpm;
	void dfs(std::pair<int,int>u){
		if(!chkin(u)||dir(u)==std::pair<int,int>{0,0}){
			return;
		}
		for(auto c: "<>^v"){
			auto v=add(u,dir(c));
			if(s[v.first][v.second]=='#'){
				tmp.insert(v);
				tmpm.insert(v);
			}
		}
//		printf("%d %d:\n",u.first,u.second);
//		for(auto v: tmp){
//			printf("(%d,%d) ",v.first,v.second);
//		}puts("");
		ans=std::max(ans,(int)tmp.size());
		for(auto v: g[u.first][u.second]){
			dfs(v);
		}
		for(auto c: "<>^v"){
			auto v=add(u,dir(c));
			if(s[v.first][v.second]=='#'){
				tmpm.erase(tmpm.find(v));
				if(!tmpm.count(v)){
					tmp.erase(v);
				}
			}
		}
	}
	void calc(){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(merge::vis[i][j]||deg[i][j]){
					continue;
				}
				if(dir(s[i][j])==std::pair<int,int>{0,0}){
					continue;
				}
				tmp=qs[i][j];
				tmpm=qsm[i][j];
				dfs({i,j});
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",&s[i][1]);
	}
	merge::init();
	top2::build();
	top2::calc();
	printf("%d\n",ans);
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			printf("(%d,%d) ",merge::fa[i][j].first,merge::fa[i][j].second);
//		}puts("");
//	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			printf("%d ",merge::vis[i][j]);
//		}puts("");
//	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 34804kb

input:

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 10ms
memory: 34180kb

input:

4 5
>v<<.
^<..#
#...#
.#>^#

output:

2

result:

ok single line: '2'

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 33520kb

input:

4 6
>>v#>v
^#>>^v
^<<#v<
.#^<<#

output:

0

result:

wrong answer 1st lines differ - expected: '5', found: '0'