Submission #81713

#TimeUsernameProblemLanguageResultExecution timeMemory
81713SaboonTeoretičar (COCI18_teoreticar)C++14
0 / 130
1587 ms263168 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; int col[maxn], edge[maxn], match[maxn]; vector <pii> g[maxn]; bool visited[maxn]; bool dfs (int v) { if (visited[v]) return false; visited[v] = 1; for (auto u : g[v]) { if (col[u.S] != 0) continue; if (match[u.F] == -1 or dfs (match[u.F])) { match[u.F] = v; edge[u.F] = u.S; return true; } } return false; } int d[maxn], dp[maxn]; int main() { ios_base::sync_with_stdio(false); int n, m, e; cin >> n >> m >> e; int Maxd = 0; for (int i = 1; i <= e; i++) { int v, u; cin >> v >> u; g[v].PB ({u, i}); d[v] ++; dp[v] ++; Maxd = max (Maxd, d[v]); Maxd = max (Maxd, dp[v]); } n = max (n, m); m = max (n, m); int tmp = e + 1; for (int i = 1; i <= n; i++) { if (d[i] < Maxd) { for (int j = 1; d[i] < Maxd and j <= m; j++) { while (d[i] < Maxd and dp[j] < Maxd) { g[i].PB ({j, tmp ++}); d[i] ++; dp[j] ++; } } } } int c = 1, cop = tmp - 1; while (cop) { memset (match, -1, sizeof match); int tmp = 0; for (int i = 1; i <= n; i++) { memset (visited, 0, sizeof visited); tmp += dfs (i); } cop -= tmp; for (int i = 1; i <= m; i++) if (match[i] != -1) col[edge[i]] = c; c ++; } cout << c - 1 << endl; for (int i = 1; i <= e; i++) 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...