제출 #542620

#제출 시각아이디문제언어결과실행 시간메모리
542620Zhora_004Usmjeravanje (COCI22_usmjeravanje)C++17
0 / 110
1 ms212 KiB
#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>& order) { vis[u] = 1; for (int& v : gp[u]) if (!vis[v]) dfs(v, gp, vis, order); order.push_back(u); } 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> order; for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, gp, vis, order); reverse(order.begin(), order.end()); vis = vector<bool>(n); int c = 0; for (int& u : order) { if (!vis[u]) { dfs1(u, tgp, vis); c++; } } 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[i].first, v = edges[i].second; if (((mask >> (m - i - 1))) & 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...