Submission #542578

#	Time	Username	Problem	Language	Result	Execution time	Memory
542578		Zhora_004	Usmjeravanje (COCI22_usmjeravanje)	C++17	0 / 110	1 ms	212 KiB

Main

#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;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60