제출 #81711

#제출 시각아이디문제언어결과실행 시간메모리
81711SaboonTeoretičar (COCI18_teoreticar)C++14
0 / 130
12049 ms25268 KiB
#include <iostream> #include <sstream> #include <queue> #include <stack> #include <vector> #include <cstring> #include <cmath> #include <map> #include <unordered_map> #include <set> #include <algorithm> #include <iomanip> #define F first #define S second #define PB push_back #define PF push_front #define MP make_pair using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int maxn = 1e5 + 37; const int maxm = 6e5 + 100; const int inf = 1e9; int col[maxn]; bool visited[maxn]; int to[2 * maxm], cap[2 * maxm], pre[2 * maxn], last[2 * maxn], pos[2 * maxn]; int n, m, e, c; int dis[2 * maxn]; bool bfs (int src, int sink) { queue <int> q; q.push (src); memset (dis, -1, sizeof dis); dis[src] = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (int ed = last[v]; ed != -1; ed = pre[ed]) { if (cap[ed] and dis[to[ed]] == -1) { dis[to[ed]] = dis[v] + 1; q.push (to[ed]); } } } return dis[sink] != -1; } int dfs (int src, int sink, int untilnow) { if (src == sink) return untilnow; int now = 0; for (int &ed = pos[src]; ed != -1; ed = pre[ed]) { if (cap[ed] and dis[to[ed]] == dis[src] + 1) { int cur = dfs (to[ed], sink, min (cap[ed], untilnow)); cap[ed] -= cur, cap[ed ^ 1] += cur, now += cur, untilnow -= cur; if (untilnow == 0) return now; } } return now; } int max_flow () { int src = n + m + 1, sink = n + m + 2; ll ret = 0; while (bfs (src, sink)) { for (int i = 1; i <= sink; i++) pos[i] = last[i]; ret += dfs (src, sink, inf); } for (int i = 0; i < 2 * e; i += 2) { if (cap[i] == 0 and col[i] == 0) { col[i] = c; cap[i ^ 1] = 0; } } return ret; } int tmp = 0; void add_edge (int fi, int se, int ca) { to[tmp] = se, cap[tmp] = ca, pre[tmp] = last[fi], last[fi] = tmp ++; to[tmp] = fi, cap[tmp] = 0, pre[tmp] = last[se], last[se] = tmp ++; } int main() { ios_base::sync_with_stdio(false); cin >> n >> m >> e; memset (last, -1, sizeof last); for (int i = 0; i < e; i++) { int v, u; cin >> v >> u; add_edge (v, u + n, 1); } int src = n + m + 1, sink = n + m + 2; for (int i = 1; i <= n; i++) add_edge (src, i, 0); for (int i = 1; i <= m; i++) add_edge (n + i, sink, 0); c = 1; int cop = e; while (cop) { for (int ed = last[src]; ed != -1; ed = pre[ed]) cap[ed] ++; for (int i = 1; i <= m; i++) cap[last[i + n]] ++; cop -= max_flow(); c ++; } cout << c - 1 << endl; for (int i = 0; i < 2 * e; i += 2) cout << col[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...