oj.uz

Submission #299912

# Submission time Handle Problem Language Result Execution time Memory
299912 2020-09-16T02:40:24 Z AM1648 Matching (COCI20_matching) C++17
110 / 110
 1714 ms 306676 KB 
/* 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 139000 KB Output is correct
2 Correct 134 ms 139004 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 139000 KB Output is correct
2 Correct 134 ms 139004 KB Output is correct
3 Correct 135 ms 138964 KB Output is correct
4 Correct 136 ms 139004 KB Output is correct
5 Correct 138 ms 139000 KB Output is correct
6 Correct 135 ms 138688 KB Output is correct
7 Correct 133 ms 138744 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 139000 KB Output is correct
2 Correct 134 ms 139004 KB Output is correct
3 Correct 135 ms 138964 KB Output is correct
4 Correct 136 ms 139004 KB Output is correct
5 Correct 138 ms 139000 KB Output is correct
6 Correct 135 ms 138688 KB Output is correct
7 Correct 133 ms 138744 KB Output is correct
8 Correct 132 ms 139256 KB Output is correct
9 Correct 133 ms 139256 KB Output is correct
10 Correct 132 ms 139304 KB Output is correct
11 Correct 136 ms 139000 KB Output is correct
12 Correct 133 ms 139260 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 139000 KB Output is correct
2 Correct 134 ms 139004 KB Output is correct
3 Correct 135 ms 138964 KB Output is correct
4 Correct 136 ms 139004 KB Output is correct
5 Correct 138 ms 139000 KB Output is correct
6 Correct 135 ms 138688 KB Output is correct
7 Correct 133 ms 138744 KB Output is correct
8 Correct 132 ms 139256 KB Output is correct
9 Correct 133 ms 139256 KB Output is correct
10 Correct 132 ms 139304 KB Output is correct
11 Correct 136 ms 139000 KB Output is correct
12 Correct 133 ms 139260 KB Output is correct
13 Correct 162 ms 145324 KB Output is correct
14 Correct 159 ms 145272 KB Output is correct
15 Correct 162 ms 145400 KB Output is correct
16 Correct 156 ms 145272 KB Output is correct
17 Correct 158 ms 145344 KB Output is correct
18 Correct 158 ms 145272 KB Output is correct
19 Correct 163 ms 145272 KB Output is correct
20 Correct 163 ms 145272 KB Output is correct
21 Correct 164 ms 144888 KB Output is correct
22 Correct 161 ms 144888 KB Output is correct
23 Correct 157 ms 143864 KB Output is correct
24 Correct 151 ms 143480 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 139000 KB Output is correct
2 Correct 134 ms 139004 KB Output is correct
3 Correct 135 ms 138964 KB Output is correct
4 Correct 136 ms 139004 KB Output is correct
5 Correct 138 ms 139000 KB Output is correct
6 Correct 135 ms 138688 KB Output is correct
7 Correct 133 ms 138744 KB Output is correct
8 Correct 132 ms 139256 KB Output is correct
9 Correct 133 ms 139256 KB Output is correct
10 Correct 132 ms 139304 KB Output is correct
11 Correct 136 ms 139000 KB Output is correct
12 Correct 133 ms 139260 KB Output is correct
13 Correct 162 ms 145324 KB Output is correct
14 Correct 159 ms 145272 KB Output is correct
15 Correct 162 ms 145400 KB Output is correct
16 Correct 156 ms 145272 KB Output is correct
17 Correct 158 ms 145344 KB Output is correct
18 Correct 158 ms 145272 KB Output is correct
19 Correct 163 ms 145272 KB Output is correct
20 Correct 163 ms 145272 KB Output is correct
21 Correct 164 ms 144888 KB Output is correct
22 Correct 161 ms 144888 KB Output is correct
23 Correct 157 ms 143864 KB Output is correct
24 Correct 151 ms 143480 KB Output is correct
25 Correct 1132 ms 306036 KB Output is correct
26 Correct 1159 ms 306676 KB Output is correct
27 Correct 1149 ms 306424 KB Output is correct
28 Correct 1159 ms 306040 KB Output is correct
29 Correct 1179 ms 304080 KB Output is correct
30 Correct 1141 ms 304116 KB Output is correct
31 Correct 1150 ms 303956 KB Output is correct
32 Correct 1137 ms 303988 KB Output is correct
33 Correct 1012 ms 287732 KB Output is correct
34 Correct 1041 ms 287476 KB Output is correct
35 Correct 122 ms 125688 KB Output is correct
36 Correct 1714 ms 299128 KB Output is correct
37 Correct 950 ms 294764 KB Output is correct
38 Correct 981 ms 292972 KB Output is correct