Submission #1243548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243548		gaga999	Usmjeravanje (COCI22_usmjeravanje)	C++20	0 / 110	4 ms	9792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define iter(x) (x).begin(), (x).end()
#define size(x) (int)(x).size()
#define INF 0x3f3f3f3f
#define lowbit(x) ((x) & -(x))
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
typedef long long ll;
typedef pair<int, int> pii;

void db() { cerr << endl; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

const int N = 4e5 + 5;
int dfn[N], low[N], ar[N], br[N], ctd, sum;
bool ans[N];
vector<int> sk, eg[N];

void dfs(int u) {
    dfn[u] = low[u] = ++ctd;
    sk.pb(u);
    for (int v : eg[u]) {
        if (!dfn[v]) {
            dfs(v);
            tmin(low[u], low[v]);
        } else if (dfn[v] < dfn[u]) {
            tmin(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        int v;
        do {
            v = sk.back();
            sk.pop_back();
            dfn[v] = INF;
        } while (v != u);
        sum++;
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int a, b, m;
    cin >> a >> b >> m;
    for (int i = 0; i < m; i++)
        cin >> ar[i] >> br[i];
    vector<int> od(m);
    iota(iter(od), 0);
    sort(iter(od), [](int x, int y) {
        return ar[x] < ar[y] || (ar[x] == ar[y] && br[x] > br[y]);
    });
    for (int i = 2; i <= a; i++)
        eg[i - 1].pb(i);
    for (int i = 2 + a; i <= a + b; i++)
        eg[i - 1].pb(i);
    int mx = 0;
    for (int i : od) {
        if (br[i] > mx)
            ans[i] = 1, eg[br[i] + a].pb(ar[i]), mx = br[i];
        else
            eg[ar[i]].pb(br[i] + a);
    }
    for (int i = 1; i <= a + b; i++)
        if (!dfn[i])
            dfs(i);
    cout << sum << '\n';
    for (int i = 0; i < m; i++)
        cout << ans[i] << " \n"[i == m - 1];
}

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