QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120470#5156. Going in CirclesPetroTarnavskyi#TL 0ms0kbC++173.2kb2023-07-06 18:44:442023-07-06 18:44:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-06 18:44:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-07-06 18:44:44]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VL = vector<LL>;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second
#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 FILL(a, b) memset(a, b, sizeof(a))

const int ALP = 26;
const int MAX = 1 << 10;

struct Edge {
	int u, v;
	int cap, flow;
};

vector<Edge> E;
vector<int> g[MAX];
int D[MAX], Q[MAX], P[MAX];
int N;

void addEdge(int u, int v, int cap) {
	g[u].push_back(SZ(E));
	E.push_back({u, v, cap, 0});
	g[v].push_back(SZ(E));
	E.push_back({v, u, 0, 0});
}

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 (int e : g[x]) {
			if (E[e].flow == E[e].cap) {
				continue;
			}
			int to = E[e].v;
			if (D[to] == -1) {
				D[to] = D[x] + 1;
				Q[qt++] = to;
			}
		}
	}
	return D[t];
}

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

int flow(int s, int t, int need) {
	int res = 0;
	while (res < need && bfs(s, t) != -1) {
		FOR(i, 0, N) {
			P[i] = 0;
		}
		while (res < need) {
			int push = dfs(s, t, 47);
			if (push == 0) {
				break;
			}
			assert(push == 1);
			res += push;
		}
	}
	assert(res == need);
	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int guesses, l;
	cin >> guesses >> l;
	string ans(l, '?');
	vector<int> cnt(ALP), black(ALP);
	vector idxEdge(ALP, vector<int>(l, -2));
	while (--guesses) {
		string s, t;
		cin >> s >> t;
		vector<int> curCnt(ALP), curBlack(ALP);
		FOR(j, 0, l) {
			if (t[j] == 'G') {
				ans[j] = s[j];
			}
			if (t[j] == 'B') {
				curBlack[s[j] - 'a'] = 1;
			}
			else {
				curCnt[s[j] - 'a']++;
			}
			if (t[j] != 'G') {
				idxEdge[s[j] - 'a'][j] = -1;
			}
		}
		FOR(i, 0, ALP) {
			if (curBlack[i]) {
				cnt[i] = curCnt[i];
				black[i] = curBlack[i];
			}
			else if (!black[i]) {
				cnt[i] = max(cnt[i], curCnt[i]);
			}
		}
	}
	int s = l + ALP, t = l + ALP + 1;
	N = l + ALP + 2;
	FOR(i, 0, ALP) {
		FOR(j, 0, l) {
			if (ans[j] == '?' && idxEdge[i][j] != -1) {
				idxEdge[i][j] = SZ(E);
				addEdge(i, ALP + j, 1);
			}
		}
	}
	FOR(j, 0, l) {
		addEdge(ALP + j, t, 1);
	}
	int f = count(ALL(ans), '?');
	FOR(i, 0, ALP) {
		flow(i, t, cnt[i]);
		f -= cnt[i];
	}
	FOR(i, 0, ALP) {
		if (!black[i]) {
			addEdge(s, i, l);
		}
	}
	flow(s, t, f);
	FOR(i, 0, ALP) {
		FOR(j, 0, l) {
			if (ans[j] == '?' && idxEdge[i][j] >= 0 && E[idxEdge[i][j]].flow > 0) {
				ans[j] = char(i + 'a');
			}
		}
	}
	cout << ans << "\n";
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

0

output:


result: