#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
//#include <bit>
//#include <ranges>
//#include <numbers>
#define itn int
#define sacnf scanf
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 1e6 + 1, inf = 1e9;
void dfs(int u, vector<vector<int>>& gp, vector<bool>& vis, vector<int>& tin, vector<int>& tout, int& timer)
{
tin[u] = timer++;
vis[u] = 1;
for (int& v : gp[u]) if (!vis[v]) dfs(v, gp, vis, tin, tout, timer);
tout[u] = timer++;
}
void dfs1(int u, vector<vector<int>>& gp, vector<bool>& vis)
{
vis[u] = 1;
for (int& v : gp[u]) if (!vis[v]) dfs1(v, gp, vis);
}
int solve(vector<vector<int>>& gp)
{
int n = sz(gp);
vector<vector<int>> tgp(n);
for (int i = 0; i < n; i++) for (int& u : gp[i]) tgp[u].push_back(i);
vector<bool> vis(n);
vector<int> tin(n), tout(n);
int timer = 1;
for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, tgp, vis, tin, tout, timer);
vector<int> vec(2 * n + 1, -1);
for (int i = 0; i < n; i++) vec[tout[i]] = i;
vis = vector<bool>(n);
int c = 0;
for (int i = 2 * n; i >= 1; i--)
{
if (vec[i] == -1) continue;
int u = vec[i];
if (vis[u]) continue;
c++;
dfs1(u, gp, vis);
}
return c;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int a, b, m;
cin >> a >> b >> m;
vector<vector<int>> gp(a + b);
for (int i = 0; i < a - 1; i++) gp[i].push_back(i + 1);
for (int i = 0; i < b - 1; i++) gp[a + i].push_back(a + i + 1);
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; i++)
{
cin >> edges[i].first >> edges[i].second;
edges[i].first--;
edges[i].second += a - 1;
}
int ans = 100, res = 0;
for (int mask = 0; mask < (1 << m); mask++)
{
vector<vector<int>> tmp = gp;
for (int i = 0; i < m; i++)
{
int u = edges[m - i - 1].first, v = edges[m - i - 1].second;
if ((mask >> i) & 1) gp[v].push_back(u);
else gp[u].push_back(v);
}
int k = solve(gp);
if (k < ans) ans = k, res = mask;
gp = tmp;
}
cout << ans << "\n";
for (int i = 0; i < m; i++) cout << ((res >> (m - i - 1)) & 1) << " ";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
