QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100368 | #4231. Rafting Trip | Beevo | WA | 13ms | 32768kb | C++23 | 2.9kb | 2023-04-25 18:26:18 | 2023-04-25 18:26:19 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
typedef long long ll;
typedef long double ld;
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 500 * 500 + 5;
int r, c;
stack<int> st;
int id, mx = 0;
vector<int> G[N];
map<int, int> freq;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
set<int> g[N], windows[N];
vector<vector<int>> comps;
int tin[N], lowLink[N], state[N], root[N], in[N];
bool valid(int x, int y) {
return x >= 0 && x < r && y >= 0 && y < c;
}
void tarjan(int u)
{
st.push(u);
state[u] = 1;
tin[u] = lowLink[u] = ++id;
for(auto &v: G[u])
{
if(!state[v])
{
tarjan(v);
lowLink[u] = min(lowLink[u], lowLink[v]);
}
else if(state[v] == 1)
lowLink[u] = min(lowLink[u], tin[v]);
}
if(tin[u] == lowLink[u])
{
while(st.top() != u) {
state[st.top()] = 2, st.pop(), root[st.top()] = u;
for (auto &i: windows[st.top()])
windows[u].insert(i);
}
state[st.top()] = 2, st.pop(), root[u] = u;
}
}
void dfs(int u) {
for (auto &i: windows[u])
freq[i]++;
mx = max(mx, (int)freq.size());
for (auto &v: g[u])
dfs(v);
for (auto &i: windows[u]) {
freq[i]--;
if (!freq[i])
freq.erase(i);
}
}
void testCase() {
cin >> r >> c;
char a[r][c];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++)
cin >> a[i][j];
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (a[i][j] == '#' || a[i][j] == '.')
continue;
if (a[i][j] == '>' && j + 1 < c)
G[i * c + j + 1].push_back(i * c + j);
if (a[i][j] == '<' && j - 1 >= 0)
G[i * c + j - 1].push_back(i * c + j);
if (a[i][j] == 'v' && i + 1 < r)
G[(i + 1) * c + j].push_back(i * c + j);
if (a[i][j] == '^' && i - 1 >= 0)
G[(i - 1) * c + j].push_back(i * c + j);
for (int k = 0; k < 4; k++) {
if (valid(i + dx[k], j + dy[k]) && a[i + dx[k]][j + dy[k]] == '#')
windows[i * c + j].insert((i + dx[k]) * c + j + dy[k]);
}
}
}
for (int i = 0; i < r * c; i++) {
if (state[i] != 2)
tarjan(i);
}
for (int i = 0; i < r * c; i++) {
for (auto &j: G[i]) {
if (root[i] != root[j]) {
in[root[j]]++;
g[root[i]].insert(root[j]);
}
}
}
for (int i = 0; i < r * c; i++) {
if (root[i] == i && !in[i])
dfs(i);
}
cout << mx;
}
signed main() {
Beevo
int t = 1;
// cin >> t;
while (t--)
testCase();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 32748kb
input:
5 6 v<<<#v v#v<.> >>v<<< ..v##^ #<<<.^
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 5ms
memory: 32644kb
input:
4 5 >v<<. ^<..# #...# .#>^#
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 9ms
memory: 32752kb
input:
4 6 >>v#>v ^#>>^v ^<<#v< .#^<<#
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 7ms
memory: 32672kb
input:
6 6 ^.>>>> ^..... ^....v ^....v #....v <<<<#v
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 4ms
memory: 32768kb
input:
6 7 ^>>>>>v ^.....v ^.#^..v ^.#^<.v ^.....v ^<<<<<<
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 13ms
memory: 32676kb
input:
3 7 >v<<<<# ^<##### #^<<<<<
output:
6
result:
ok single line: '6'
Test #7:
score: -100
Wrong Answer
time: 4ms
memory: 32676kb
input:
3 5 ><.v# ##.^# ...#.
output:
0
result:
wrong answer 1st lines differ - expected: '3', found: '0'