QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625457#4231. Rafting TripNYCU_CartesianTree#Compile Error//C++203.8kb2024-10-09 19:25:202024-10-09 19:25:20

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 19:25:20]
  • 评测
  • [2024-10-09 19:25:20]
  • 提交

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;
}

詳細信息

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...