Submission #1243549

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

Main

#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 400005
using namespace std;
int na, nb, n, m, tot, num, mx, cnt, ans, sum[N], sta[N * 10], dfn[N << 1], low[N << 1];
bool bj[N << 1];
struct node {
    int x, y, id;
} edg[N];
struct edge {
    int to, next, head;
} a[N * 3];
bool cmp(node x, node y) {
    if (x.x < y.x)
        return true;
    if (x.x > y.x)
        return false;
    return x.y > y.y;
}
void add(int x, int y) {
    a[++tot].to = y;
    a[tot].next = a[x].head;
    a[x].head = tot;
}
void dfs(int x) {
    dfn[x] = low[x] = ++cnt;
    sta[++num] = x;
    bj[x] = true;
    for (int i = a[x].head; i; i = a[i].next) {
        int y = a[i].to;
        if (!dfn[y])
            dfs(y), low[x] = min(low[x], low[y]);
        else if (bj[y])
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) {
        ++ans;
        while (sta[num] != x)
            bj[sta[num--]] = false;
        bj[sta[num--]] = false;
    }
}
int main() {
    scanf("%d%d", &na, &nb);
    for (int i = 1; i < na; ++i)
        add(i, i + 1);
    for (int i = 1; i < nb; ++i)
        add(i + na, i + na + 1);
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d", &edg[i].x, &edg[i].y), edg[i].id = i;
    sort(edg + 1, edg + m + 1, cmp);
    for (int i = 1; i <= m; ++i) {
        if (edg[i].y > mx)
            mx = edg[i].y, add(edg[i].y + na, edg[i].x), sum[edg[i].id] = 1;
        else
            add(edg[i].x, edg[i].y + na), sum[edg[i].id] = 0;
    }
    n = na + nb;
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            dfs(i);
    printf("%d\n", ans);
    for (int i = 1; i <= m; ++i)
        printf("%d ", sum[i]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d%d", &na, &nb);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
Main.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d%d", &edg[i].x, &edg[i].y), edg[i].id = i;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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