QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#95582#5470. Hasty Santa ClausPetroTarnavskyi#Compile Error//C++173.9kb2023-04-10 18:52:102023-04-10 18:52:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-10 18:52:11]
  • 评测
  • [2023-04-10 18:52:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int MAX = 10047;

struct edge
{
	int x, y;
	LL c, f;
};
vector<edge> E;

VI g[MAX];
int D[MAX];
int Q[MAX];
int Ptr[MAX];
int N;

const int LINF = 1e9 + 47;

void add_edge(int x, int y, LL c)
{
	edge e;
	e.x = x; e.y = y;
	e.c = c; e.f = 0;
	g[x].PB(SZ(E));
	E.PB(e);
	e.x = y; e.y = x;
	e.c = 0; e.f = 0;
	g[x].PB(SZ(E));
	E.PB(e);
}

int bfs(int s, int t)
{
	FOR(i, 0, N)
		D[i] = -1;
	D[s] = 0;
	Q[0] = s;
	int qh = 0, qt = 1;
	while (qh < qt && D[t] == -1)
	{
		int x = Q[qh++];
		FOR (i, 0, SZ(g[x]))
		{
			int e = g[x][i];
			if (E[e].f == E[e].c) continue;
			int to = E[e].y;
			
			if (D[to] == -1)
			{
				D[to] = D[x] + 1;
				Q[qt++] = to;
			}

		}
	}
	return D[t];
}

LL dfs(int x, int t, LL flow)
{
	if (x == t || flow == 0) return flow;
	for (; Ptr[x] < SZ(g[x]); Ptr[x]++)
	{
		int e = g[x][Ptr[x]];
		LL c = E[e].c;
		LL f = E[e].f;
		int to = E[e].y;
		if (c == f) continue;
		if (D[to] == D[x] + 1)
		{
			LL push = dfs(to, t, min(flow, c - f));
			if (push > 0)
			{
				E[e].f += push;
				E[e ^ 1].f -= push;
				return push;
			}
		}
	}
	return 0;
}

LL Flow(int s, int t)
{
	LL res = 0;
	while (bfs(s, t) != -1)
	{
		FOR(i, 0, N)
			Ptr[i] = 0;
		while (true)
		{
			LL push = dfs(s, t, LINF);
			if (push == 0) break;
			res += push;
		}
	}
	return res;
}

PII d[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool used[147][147];

vector<PII> path[2];
int c;
int n, m;
vector<string> v;
int k = 1;
int dir[2];

bool ok(int x, int y)
{
	return 0 <= x && x < n && 0 <= y && y < m && v[x][y] != '#';
}

void dfs(int x, int y, int t)
{
	used[x][y] = 1;
	path[c].PB({x, y});
	if (v[x][y] == 'T')
		return;
	if (v[x][y] == 'U')
		return;
	FOR(i, 0, 4)
	{
		int nx = x + d[(t + 4 + i * k) % 4].first;
		int ny = y + d[(t + 4 + i * k) % 4].first;
		if (ok(nx, ny))
		{
			if (used[nx][ny]) return;
			dfs(nx, ny, (t - k + 4) % 4);
			return;
		}		
	}
}

bool ur[147][147];
bool uc[147][147];

int f(int x, int y, int nx, int ny)
{
	if (x == nx) return bc[x][min(y, ny)] ? 1 : LINF;
	if (y == ny) return br[min(x, nx)][y] ? 1 : LINF;
	assert(0);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	v.resize(n);
	int x = -1, y = -1;
	FOR(i, 0, n)
	{
		cin >> v[i];
		FOR(j, 0, m) if (v[i][j] == 'S') x = i, y = j;
	}
	if (x == 0) dir[0] = 0, dir[1] = 2;
	if (y == 0) dir[0] = 1, dir[1] = 3;
	if (x == n - 1) dir[0] = 2, dir[1] = 0;
	if (y == 0) dir[0] = 3, dir[1] = 1;
	
	dfs(x, y, dir[c]);
	int cnt = 0;
	if (v[path[c].back().first][path[c].back().second] == 'T') cnt++;
	c++;
	dfs(x, y, dir[c]);
	if (v[path[c].back().first][path[c].back().second] == 'T') cnt++;
	if (cnt == 2)
	{
		cout << 0 << '\n';
		return 0;
	}
	if (cnt == 0)
	{
		cout << -1 << '\n';
		return 0;
	}
	if (v[path[1].back().first][path[1].back().second] == 'T')
	{
		path[0] = path[1];
	}
	int q;
	cin >> q;
	FOR(i, 0, q)
	{
		int a, b;
		char c;
		cin >> a >> b >> c;
		a--, b--;
		if (c == 'b')
			ur[a][b] = 1;
		else
			uc[a][b] = 1;
	}
	set<PII> s(ALL(path[0]));
	N = n * m;
	FOR(i, 0, n)
	{
		FOR(j, 0, m)
		{
			if (v[i][j] == '#') continue;
			int V = i * n + j;
			if (s.count({i, j})) add_edge(V, N, LINF);
			FOR(k, 0, 4)
			{
				int nx = i + d[k].first;
				int ny = j + d[k].second;
				int cap = f(i, j, nx, ny);
				if (ok(nx, ny))
				{
					add_edge(V, nx * n + ny, cap);
				}
			}
		}
	}
	
	int Fl = Flow()
	
	return 0;
}

详细

answer.code: In function ‘int f(int, int, int, int)’:
answer.code:156:29: error: ‘bc’ was not declared in this scope; did you mean ‘uc’?
  156 |         if (x == nx) return bc[x][min(y, ny)] ? 1 : LINF;
      |                             ^~
      |                             uc
answer.code:157:29: error: ‘br’ was not declared in this scope; did you mean ‘ur’?
  157 |         if (y == ny) return br[min(x, nx)][y] ? 1 : LINF;
      |                             ^~
      |                             ur
answer.code: In function ‘int main()’:
answer.code:234:22: error: too few arguments to function ‘LL Flow(int, int)’
  234 |         int Fl = Flow()
      |                  ~~~~^~
answer.code:98:4: note: declared here
   98 | LL Flow(int s, int t)
      |    ^~~~