QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #625630 | #4231. Rafting Trip | NYCU_CartesianTree | TL | 41ms | 33340kb | C++20 | 3.8kb | 2024-10-09 20:08:47 | 2024-10-09 20:08:51 |
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 cnt = 0;
int dfs(int v){
// cerr << v << '\n';
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[id]++;
// 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();
for(auto i : graph[top]){
degree[i]--;
if(degree[i] == 0){
que.push(i);
}
}
}
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]){
nnnnn++;
assert(nnnnn <= 250000);
vis[now] = 0;
for(auto j : graph[now]){
if(!not_circle[j])
continue;
ans = max(ans, circle_cnt + dfs(j));
}
now = to[now];
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5656kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5592kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5696kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5852kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
3 5 ><.v# ##.^# ...#.
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
7 3 ### #># ### ... ### #>. ###
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5572kb
input:
2 2 >. .#
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 2 .. .v
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 41ms
memory: 29816kb
input:
498 498 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
41195
result:
ok single line: '41195'
Test #12:
score: 0
Accepted
time: 35ms
memory: 33340kb
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
24926
result:
ok single line: '24926'
Test #13:
score: -100
Time Limit Exceeded
input:
500 500 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...