QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625680 | #4231. Rafting Trip | NYCU_CartesianTree | AC ✓ | 44ms | 36560kb | C++20 | 3.9kb | 2024-10-09 20:26:14 | 2024-10-09 20:26:14 |
Judging History
answer
//============================================================================
// Name : G.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
#pragma GCC optimize("03,unroll-loops,Ofast,inline,-ffast-math")
#pragma GCC target("avx,popcnt,sse4,abm,sse2,sse3,mmx")
char a[N][N];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0 , 1}}; // up down left right
int degree[N * N];
int to[N * N];
vector<int> graph[N * N];
bool vis[N * N], dfs_vis[N * N], visit_site[N][N], not_circle[N * N];
int n, m;
int ccccc=0;
int cnt = 0;
int dfs(int v){
// cerr << v << '\n';
ccccc++;
if(ccccc>550000) assert(0);
int x = (v - 1) / m + 1, y = (v - 1) % m + 1;
dfs_vis[v] = 1;
vector<pair<int, int> > add_site;
for(int j = 0; j < 4; j++){
int tox = x + dir[j][0], toy = y + dir[j][1];
if(tox <= 0 || tox > n || toy <= 0 || toy > m)
continue;
if(a[tox][toy] == '#' && !visit_site[tox][toy]){
visit_site[tox][toy] = 1;
cnt++;
add_site.push_back({tox, toy});
}
}
int maxn = cnt;
for(auto i : graph[v]){
if(dfs_vis[i] || !not_circle[i]){
continue;
}
maxn = max(maxn, dfs(i));
}
for(auto i : add_site){
visit_site[i.first][i.second] = 0;
cnt--;
}
return maxn;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n * m; i++){
not_circle[i] = 1;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
vector<int> lien;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == '.' || a[i][j] == '#')
continue;
int id = (i - 1) * m + j;
int x, y;
if(a[i][j] == '^'){
x = i + dir[0][0];
y = j + dir[0][1];
}else if(a[i][j] == 'v'){
x = i + dir[1][0];
y = j + dir[1][1];
}else if(a[i][j] == '<'){
x = i + dir[2][0];
y = j + dir[2][1];
}else if(a[i][j] == '>'){
x = i + dir[3][0];
y = j + dir[3][1];
}
int id2 = (x - 1) * m + y;
if(x <= 0 || x > n || y <= 0 || y > m || a[x][y] == '.' || a[x][y] == '#'){
lien.push_back(id);
continue;
}
graph[id2].push_back(id);
to[id] = id2;
degree[id2]++;
// cerr << id2 << ' ' << id << '\n';
}
}
// return 0;
queue<int> que;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int id = (i - 1) * m + j;
if(degree[id] == 0){
que.push(id);
}
}
}
while(!que.empty()){
int top = que.front();
que.pop();
if(to[top] != 0){
degree[to[top]]--;
if(degree[to[top]] == 0){
que.push(to[top]);
}
}
}
// for(int i = 1; i <= n * n; i++){
// cerr << i << ' ' << degree[i] << '\n';
// }
int ans = 0;
for(int i = 1; i <= n * m; i++){
if(degree[i] != 0 && not_circle[i]){
not_circle[i] = 0;
int now = i, circle_cnt = 0;
vector<pair<int, int> > add_site;
int nnnnn=0;
while(!vis[now]){
vis[now] = 1;
not_circle[now] = 0;
int x = (now - 1) / m + 1, y = (now - 1) % m + 1;
for(int j = 0; j < 4; j++){
int tox = x + dir[j][0], toy = y + dir[j][1];
if(tox <= 0 || tox > n || toy <= 0 || toy > m)
continue;
if(a[tox][toy] == '#' && !visit_site[tox][toy]){
visit_site[tox][toy] = 1;
circle_cnt++;
add_site.push_back({tox, toy});
}
}
now = to[now];
}
ans = max(ans, circle_cnt);
now = i;
while(vis[now]){
vis[now] = 0;
// cerr << now << '\n';
for(auto j : graph[now]){
if(!not_circle[j]||dfs_vis[j])
continue;
ans = max(ans, circle_cnt + dfs(j));
}
now = to[now];
}
// cerr << '\n';
for(auto j : add_site){
visit_site[j.first][j.second] = 0;
}
}
}
for(auto i : lien){
ans = max(ans, dfs(i));
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5612kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5556kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5888kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5604kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 0ms
memory: 5664kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 37ms
memory: 29728kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
41195
result:
ok single line: '41195'
Test #12:
score: 0
Accepted
time: 32ms
memory: 33780kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24926
result:
ok single line: '24926'
Test #13:
score: 0
Accepted
time: 31ms
memory: 24632kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24924
result:
ok single line: '24924'
Test #14:
score: 0
Accepted
time: 33ms
memory: 17584kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
2056
result:
ok single line: '2056'
Test #15:
score: 0
Accepted
time: 32ms
memory: 17352kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
970
result:
ok single line: '970'
Test #16:
score: 0
Accepted
time: 36ms
memory: 17152kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
687
result:
ok single line: '687'
Test #17:
score: 0
Accepted
time: 37ms
memory: 16932kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
481
result:
ok single line: '481'
Test #18:
score: 0
Accepted
time: 24ms
memory: 16408kb
input:
500 500 .>^v.^<<^<<<<<<....><v#....^.#.^..#.^<<<<#..#.><v.v..>>^<<..###..^<v..#>>>#.....^>^#.##.#......#.....#v#.>v.v#..##.#.^>>>>>v..#.v<..^...^..^#....#..>v.#^<..^^v..^.....vv..v...#^.v>>v#.#.#..#.v.^v<<......^#<.v...v>>^^<^#..^^v.^..^..^...#.#.^...^^<<<...##...v.........^.^.....>>>>>#.....><<<^.....
output:
13
result:
ok single line: '13'
Test #19:
score: 0
Accepted
time: 32ms
memory: 17236kb
input:
500 499 <<<<<#v.^.^v>v<^^.^<>><>^.^v.><^.v^<.^^#..v#>>><<<v^<>>^>>v<<<<^^^^#<>v>^<>>>^>^<<<#^^#v<<<<<<<<v>#v<<v^v.v^<<^<##><<^^<>^<#^^.^#>v^<<^>>>>v^.^>>^<#^>v^#<<<<^><^#.v^>^.^^v<.#^<<<v.v^^^#^<<.>^^#vvv<<^..>#v<.^<<<>>v>>>^.#v#>>#^<<^v<.>^#^.><^<>#^<<^^^^<<<<.><..><<#^<<>>>>>>>^^<>#>v<><#^^><v<><>...
output:
13
result:
ok single line: '13'
Test #20:
score: 0
Accepted
time: 42ms
memory: 17740kb
input:
499 500 v^^.#<^^^..>^.v^<^<<v>^<<^>^#^^v^.>vv<v.>v.^<<<<<.v.^>>v<^#v##<^<<<vv^^^^^.>^v...#>v#.#v^^>^<<>v>>v#<><v>#vv<>>v^.>v<^<v>^#>^<<<>^>v^^..vv<<<v#<<.^^<<.v^<>^<<v^<><<vvv#<<v.##^><vv^>^>^v^##>v>>>^^v.#>^.^.^#.v<<<<^#.^^<^^#.>v.#^<^^^..v<>v<.#.^.v#v^..#>v<vv<<<<<>#v^v.#>#..><>>^...^.#><^>>>>>>>>...
output:
12
result:
ok single line: '12'
Test #21:
score: 0
Accepted
time: 44ms
memory: 18176kb
input:
500 500 ^v>>v>v<>>>^#>v<^<>>>>v<<<^v.>^><.v>v<>^>vv^v>>><.>^v>>#^<<<>^<vv^^>>>v<v.^^v>v<vv<^>vv^<<vv<^^^^>>^^<^>>^^>>#<v^>v>>^<v<#<<vv<<<<<<<<<<<<<<<<<<^^v>^^<^^^v^<<#><<><>^>^>>>v<>>v><<^^<v^v<>>>^<v>>^vv>>v>>>v>v.v.v<v>#^<<<<<<<<<<.>v>^<<<<><^v<>v#<.^>^>^vv.v<>^v#<##^v^>^#v<v<<<<>>>#^>v>>>>>v^^>>^...
output:
11
result:
ok single line: '11'
Test #22:
score: 0
Accepted
time: 12ms
memory: 12588kb
input:
500 500 ######<##############^#####>########v##########v###############################<######<#####>######v########################v####v##########>######v####<##########^#<##################<#####<########v#######<^####^v#####################^v####>#########^###########.v####<##########v##########...
output:
10
result:
ok single line: '10'
Test #23:
score: 0
Accepted
time: 35ms
memory: 18292kb
input:
500 500 <^^<^>><##<v>^>>#<^>v<^v<^^^<<><^^^<^v<^<^^^v#v<<<vv<vv^>>>>>>><vv<<<<>vv^^<^^>><<^<^>^<>^><v>^>^vv>^>^><<^v>^<<>vvv><>>>>>^vv>>#<>>>^^<v<<<^>v^^^<#<<^v^<<>>>>><##^>>#<<<<<<<<^><<<<<<^v^vv.^><>v^^v<v^>vv#^<<<^<<>#>^>>v>^>^^<^>>>^<v<<<v#v^>^^^<^<>^^<vv<<<#>v<v<^v^#^^>>>>^v^^<<>>#>>v<<<<v^<vv>...
output:
14
result:
ok single line: '14'
Test #24:
score: 0
Accepted
time: 1ms
memory: 6172kb
input:
500 2 <v .# .# vv #< v^ <> <^ v. #> ># v^ #< ^# #< >v <> ^. #. << #< >> ># >> #< #v ^# << #^ #v #^ ^. ^# v# ## #> << #^ v^ <v ^# ^> ># .v #^ <# ## .v ># ## ^# ^< ^^ <# .> <^ v< >< <v #v ## #> #> ## ## ^# v> >< .^ v# #^ v> <v ## ## #> >v #v >< .# #. ^# #. ># v< ># #< <^ ^# #. <> #^ .v ## .v .v .# >> ...
output:
6
result:
ok single line: '6'
Test #25:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
2 500 v##v#>>>>^>>#.##<<.>>^#.v^>^^>##^>^^##v^^#.^<#<###<##v#^>^^.v>v#<^<<##^#^.#<##>#>>#v#>^#vv.^v#>v.####.>#.>>v#<.>#^..#<v##>>>^#v###^<#^#<#^^#>v^>###>>>><#^#v>v.v<^.#v.v##<.####<<<^#>^#^#<#>v#>#>^#>##.>>>^^<##<^^<v<...#v#.#<>>>>#.##.v#<.##.^#<^>#<<vv^>^#^..#<^##^^#<<##.vv<v^#<><.#<<.^^##^.#<v.##...
output:
5
result:
ok single line: '5'
Test #26:
score: 0
Accepted
time: 24ms
memory: 33980kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
31270
result:
ok single line: '31270'
Test #27:
score: 0
Accepted
time: 26ms
memory: 36560kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
123584
result:
ok single line: '123584'
Test #28:
score: 0
Accepted
time: 17ms
memory: 15468kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
331
result:
ok single line: '331'
Test #29:
score: 0
Accepted
time: 23ms
memory: 15900kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
1234
result:
ok single line: '1234'
Test #30:
score: 0
Accepted
time: 21ms
memory: 15632kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
281
result:
ok single line: '281'
Test #31:
score: 0
Accepted
time: 24ms
memory: 15496kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
996
result:
ok single line: '996'