Submission #299912

#	Time	Username	Problem	Language	Result	Execution time	Memory
299912		AM1648	Matching (COCI20_matching)	C++17	110 / 110	1714 ms	306676 KiB

matching

/* be name khoda */

// #define long_enable
#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <vector>
#include <fstream>
#include <set>
#include <map>
using namespace std;

#ifdef long_enable
typedef long long int ll;
#else
typedef int ll;
#endif

typedef pair<ll, ll> pii;
typedef pair<pii, ll> ppi;
typedef pair<ll, pii> pip;
typedef vector<ll> vi;
typedef vector<pii> vpii;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define fori(i, n) forifrom (i, 0, n)
#define forir(i, n) forirto (i, n, 0)

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define smin(a, b) a = min(a, (b))
#define smax(a, b) a = max(a, (b))

#define debug(x) cout << #x << " -> " << (x) << endl
#define debug2(x, y) cout << #x << ' ' << #y << " -> " << (x) << ' ' << (y) << endl
#define debug3(x, y, z) cout << #x << ' ' << #y << ' ' << #z << " -> " << (x) << ' ' << (y) << ' ' << (z) << endl
#define debug4(x, y, z, t) cout << #x << ' ' << #y << ' ' << #z << ' ' << #t << " -> " << (x) << ' ' << (y) << ' ' << (z) << ' ' << (t) << endl
#define debuga(x, n) cout << #x << " -> "; fori (i1_da, n) { cout << (x)[i1_da] << ' '; } cout << endl
#define debugaa(x, n, m) cout << #x << " ->\n"; fori (i1_daa, n) { fori (i2_daa, m) { cout << (x)[i1_daa][i2_daa] << ' '; } cout << '\n'; } cout << endl

const ll MOD = 1000000007;
const ll INF = 2000000000;
const long long BIG = 1446803456761533460LL;

#define XL (x << 1)
#define XR (XL | 1)
#define MD ((l + r) >> 1)
#define Add(a, b) a = ((a) + (b)) % MOD
#define Mul(a, b) a = (1LL * (a) * (b)) % MOD

// -----------------------------------------------------------------------

const ll maxn = 100010;
const ll maxv = 5000000;

ll n, vn, V[maxn][2], H[maxn][2], Vi[maxn][2], Hi[maxn][2], seg[maxn * 4];
ll scc[maxv], sccn, st[maxv], sn, stk[maxv], up[maxv];
pii P[maxn];
vi out[maxv];
bool fst[maxn], instk[maxv], val[maxv];

inline ll VL(ll x) {
    return x << 1;
}

inline ll HL(ll y)  {
    return y << 1 ^ 1;
}

void halt() {
    cout << "NE\n";
    exit(0);
}

void add_edge(ll a, ll b) {
    out[a].pb(b);
    out[b ^ 1].pb(a ^ 1);
}

void process_points() {
    fori (i, n) {
        auto [x, y] = P[i];
        if (!V[x][1] && !H[y][1]) halt();
        else if (V[x][1] && !H[y][1]) {
            add_edge(VL(x) << 1 ^ 1, VL(x) << 1);
        } else if (!V[x][1] && H[y][1]) {
            add_edge(HL(y) << 1 ^ 1, HL(y) << 1);
        } else {
            add_edge(VL(x) << 1 ^ 1, HL(y) << 1);
            add_edge(VL(x) << 1, HL(y) << 1 ^ 1);
        }
    }
}

void build(ll x = 1, ll l = 0, ll r = maxn) {
    seg[x] = vn++;
    if (r - l > 1) {
        build(XL, l, MD);
        build(XR, MD, r);
        add_edge(seg[x] << 1 ^ 1, seg[XL] << 1 ^ 1);
        add_edge(seg[x] << 1 ^ 1, seg[XR] << 1 ^ 1);
    }
}

void conn_lr(ll li, ll ri, ll v, ll x = 1, ll l = 0, ll r = maxn) {
    if (li >= r || l >= ri) {
    } else if (li <= l && r <= ri) {
        add_edge(v << 1, seg[x] << 1 ^ 1);
    } else {
        conn_lr(li, ri, v, XL, l, MD);
        conn_lr(li, ri, v, XR, MD, r);
    }
}

void change(ll p, ll v, ll x = 1, ll l = 0, ll r = maxn) {
    if (r - l == 1) {
        seg[x] = v;
    } else {
        if (p < MD) {
            change(p, v, XL, l, MD);
        } else {
            change(p, v, XR, MD, r);
        }
        seg[x] = vn++;
        add_edge(seg[x] << 1 ^ 1, seg[XL] << 1 ^ 1);
        add_edge(seg[x] << 1 ^ 1, seg[XR] << 1 ^ 1);
    }
}

void sweepline() {
    vn = maxn * 2;
    build();
    fori (y, maxn) {
        if (H[y][1]) conn_lr(H[y][0] + 1, H[y][1], HL(y));
        fori (i, 2) if (H[y][i]) {
            ll x = H[y][i];
            if (!fst[x]) {
                change(x, VL(x));
            } else {
                ++vn;
                change(x, vn - 1);
            }
            fst[x] ^= 1;
        }
    }
}

ll stt;
void dfs(ll x) {
    st[x] = up[x] = stt++;
    instk[x] = 1;
    stk[sn++] = x;
    for (auto y : out[x]) {
        if (!st[y]) {
            dfs(y);
            smin(up[x], up[y]);
        } else if (instk[y]) {
            smin(up[x], st[y]);
        }
    }
    if (st[x] == up[x]) {
        ll y;
        do {
            y = stk[--sn];
            scc[y] = sccn;
            instk[y] = 0;
        } while (y != x);
        ++sccn;
    }
}

void two_sat() {
    stt = 1;
    fori (i, vn << 1) {
        if (!st[i]) dfs(i);
    }
    fori (i, vn) {
        if (scc[i << 1] == scc[i << 1 ^ 1]) halt();
        val[i] = scc[i << 1] < scc[i << 1 ^ 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n;
    fori (i, n) {
        ll x, y; cin >> x >> y;
        P[i] = {x, y};
        if (V[x][0] == 0) V[x][0] = y, Vi[x][0] = i;
        else {
            V[x][1] = y, Vi[x][1] = i;
            if (V[x][0] > V[x][1]) swap(V[x][0], V[x][1]), swap(Vi[x][0], Vi[x][1]);
        }
        if (H[y][0] == 0) H[y][0] = x, Hi[y][0] = i;
        else {
            H[y][1] = x, Hi[y][1] = i;
            if (H[y][0] > H[y][1]) swap(H[y][0], H[y][1]), swap(Hi[y][0], Hi[y][1]);
        }
    }
    process_points();
    sweepline();
    two_sat();

    cout << "DA\n";
    fori (i, maxn) {
        if (val[VL(i)] && V[i][1]) cout << Vi[i][0] + 1 << ' ' << Vi[i][1] + 1 << '\n';
        if (val[HL(i)] && H[i][1]) cout << Hi[i][0] + 1 << ' ' << Hi[i][1] + 1 << '\n';
    }

}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 52 / 52