QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #625457 | #4231. Rafting Trip | NYCU_CartesianTree# | Compile Error | / | / | C++20 | 3.8kb | 2024-10-09 19:25:20 | 2024-10-09 19:25:20 |
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;
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], visit_site[N][N], not_circle[N * N], is_end[N * N];
int n, m;
int cnt = 0;
int dfs(int v){
int x = (v - 1) / m + 1, y = (v - 1) % m + 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(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() {
int n, m;
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(a[i][j] == '.' || a[i][j] == '#'){
lien.push_back(id2);
}
if(x <= 0 || x > n || y <= 0 || y > m){
lien.push_back(id);
is_end[id] = 1;
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){
// cerr << i << ' ' << j << '\n';
// cerr << id << '\n';
que.push(id);
}
else if(is_end[id]){
// cerr << i << ' ' << j << '\n';
// cerr << id << '\n';
que.push(id);
degree[id] = 0;
}
}
}
while(!que.empty()){
int top = que.front();
// cerr << top << '\n';
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;
while(!vis[now]){
cerr << now << '\n';
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;
for(auto j : graph[now]){
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;
}
Details
answer.code:17:1: error: ‘vector’ does not name a type
17 | vector<int> graph[N * N];
| ^~~~~~
answer.code: In function ‘int dfs(int)’:
answer.code:23:16: error: ‘pair’ was not declared in this scope
23 | vector<pair<int, int> > add_site;
| ^~~~
answer.code:1:1: note: ‘std::pair’ is defined in header ‘<utility>’; did you forget to ‘#include <utility>’?
+++ |+#include <utility>
1 | //============================================================================
answer.code:23:9: error: ‘vector’ was not declared in this scope
23 | vector<pair<int, int> > add_site;
| ^~~~~~
answer.code:1:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
+++ |+#include <vector>
1 | //============================================================================
answer.code:23:21: error: expected primary-expression before ‘int’
23 | vector<pair<int, int> > add_site;
| ^~~
answer.code:31:25: error: ‘add_site’ was not declared in this scope
31 | add_site.push_back({tox, toy});
| ^~~~~~~~
answer.code:35:22: error: ‘graph’ was not declared in this scope
35 | for(auto i : graph[v]){
| ^~~~~
answer.code:39:24: error: ‘max’ was not declared in this scope; did you mean ‘maxn’?
39 | maxn = max(maxn, dfs(i));
| ^~~
| maxn
answer.code:41:22: error: ‘add_site’ was not declared in this scope
41 | for(auto i : add_site){
| ^~~~~~~~
answer.code: In function ‘int main()’:
answer.code:50:9: error: ‘cin’ was not declared in this scope
50 | cin >> n >> m;
| ^~~
answer.code:1:1: note: ‘std::cin’ is defined in header ‘<iostream>’; did you forget to ‘#include <iostream>’?
+++ |+#include <iostream>
1 | //============================================================================
answer.code:59:9: error: ‘vector’ was not declared in this scope
59 | vector<int> lien;
| ^~~~~~
answer.code:59:9: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
answer.code:59:16: error: expected primary-expression before ‘int’
59 | vector<int> lien;
| ^~~
answer.code:81:33: error: ‘lien’ was not declared in this scope
81 | lien.push_back(id2);
| ^~~~
answer.code:84:33: error: ‘lien’ was not declared in this scope
84 | lien.push_back(id);
| ^~~~
answer.code:90:25: error: ‘graph’ was not declared in this scope
90 | graph[id2].push_back(id);
| ^~~~~
answer.code:99:9: error: ‘queue’ was not declared in this scope
99 | queue<int> que;
| ^~~~~
answer.code:1:1: note: ‘std::queue’ is defined in header ‘<queue>’; did you forget to ‘#include <queue>’?
+++ |+#include <queue>
1 | //============================================================================
answer.code:99:15: error: expected primary-expression before ‘int’
99 | queue<int> que;
| ^~~
answer.code:106:33: error: ‘que’ was not declared in this scope
106 | que.push(id);
| ^~~
answer.code:111:33: error: ‘que’ was not declared in this scope
111 | que.push(id);
| ^~~
answer.code:116:16: error: ‘que’ was not declared in this scope
116 | while(!que.empty()){
| ^~~
answer.code:120:30: error: ‘graph’ was not declared in this scope
120 | for(auto i : graph[top]){
| ^~~~~
answer.code:132:32: error: ‘pair’ was not declared in this scope
132 | vector<pair<int, int> > add_site;
| ^~~~
answer.code:132:32: note: ‘std::pair’ is defined in header ‘<utility>’; did you forget to ‘#include <utility>’?
answer.code:132:37: error: expected primary-expression before ‘int’
132 | vector<pair<int, int> > add_site;
| ^~~
answer.code:134:33: error: ‘cerr’ was not declared in this scope
134 | cerr << now << '\n';
| ^~~~
answer.code:134:33: note: ‘std::cerr’ is defined in header ‘<iostream>’; did you forget to ‘#include <iostream>’?
answer.code:145:49: error: ‘add_site’ was not declared in this scope
145 | add_site.push_back({tox, toy});
| ^~~~~~~~
answer.code:150:31: error: ‘max...