QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #54577 | #4231. Rafting Trip | YL1F4# | WA | 9ms | 35144kb | C++ | 4.6kb | 2022-10-09 19:22:42 | 2022-10-09 19:22:44 |
Judging History
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]=='#'){
// printf("ad %d %d to %d %d\n",v.first,v.second,sr.first,sr.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];
bool vis[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]){
auto p=merge::fa[i][j];
if(!vis[p.first][p.second]){
vis[p.first][p.second]=1;
// printf("calc %d %d\n",p.first,p.second);
tmp=qs[p.first][p.second];
tmpm=qsm[p.first][p.second];
dfs(p);
}
continue;
}
if(dir(s[i][j])==std::pair<int,int>{0,0}){
continue;
}
// printf("calc %d %d\n",i,j);
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;
}
/*
7 7
>>>>v>#
..^v<><
#^>>>>^
###^v#v
>>>^##v
^<<<<<<
^#...^#
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 33936kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 4ms
memory: 34080kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 9ms
memory: 34036kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 6ms
memory: 34248kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 8ms
memory: 34592kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 4ms
memory: 35144kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: -100
Wrong Answer
time: 6ms
memory: 34240kb
input:
3 5 ><.v# ##.^# ...#.
output:
1
result:
wrong answer 1st lines differ - expected: '3', found: '1'