QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#120470 | #5156. Going in Circles | PetroTarnavskyi# | TL | 0ms | 0kb | C++17 | 3.2kb | 2023-07-06 18:44:44 | 2023-07-06 18:44:48 |
Judging History
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";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
0