Submission #228334

#	Time	Username	Problem	Language	Result	Execution time	Memory
228334		VEGAnn	Teoretičar (COCI18_teoreticar)	C++14	0 / 130	2509 ms	32464 KiB

teoreticar

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ft first
#define sd second
#define MP make_pair
#define sz(x) ((int)x.size())
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int M = 700100;
const int oo = 2e9;
stack<pii> st;
vector<int> g[2][N];
vector<pii> vc;
int col[M], l, r, m, deep, x[M], y[M], tt = 0, mrk[2][N], ptr[2][N], used[M], n, lst;

void calc(vector<int> &edges){
    bool bad = 0;

    tt++;
    vc.clear();

    for (int cr : edges){
        int v = x[cr], u = y[cr];

        if (mrk[0][v] < tt) {
            mrk[0][v] = tt;
            vc.PB(MP(v, 0));
            g[0][v].clear();
            ptr[0][v] = 0;
        }

        if (mrk[1][u] < tt) {
            mrk[1][u] = tt;
            vc.PB(MP(u, 1));
            g[1][u].clear();
            ptr[1][u] = 0;
        }

        g[0][v].PB(cr);
        g[1][u].PB(cr);

        if (sz(g[0][v]) > 1 || sz(g[1][u]) > 1)
            bad = 1;
    }

    if (!bad) return;

    g[0][n].clear();
    g[1][n].clear();

    ptr[1][n] = ptr[0][n] = 0;
    lst = m;

    for (pii cr : vc) {
        int v = cr.ft;
        int tp = cr.sd;

        if (sz(g[tp][v]) & 1){
            x[lst] = n; y[lst] = v;

            if (!tp) swap(x[lst], y[lst]);

            g[tp][v].PB(lst);
            g[tp ^ 1][n].PB(lst);
            lst++;
        }
    }

    if (sz(g[0][n]) & 1){
        x[lst] = n; y[lst] = n;
        g[0][n].PB(lst);
        g[1][n].PB(lst);
        lst++;
    }

    tt++;

    int ite = 0;

    for (pii vr : vc){
        int v = vr.ft, tp = vr.sd;

        if (ptr[tp][v] != 0) continue;

        st.push(vr);

        while (sz(st)){
            pii cr = st.top();
            bool was = 0;
            v = cr.ft; tp = cr.sd;

            for (; ptr[tp][v] < sz(g[tp][v]); ptr[tp][v]++){
                int id = g[tp][v][ptr[tp][v]];

                if (used[id] == tt) continue;

                was = 1;

                int nw = (tp == 0 ? y[id] : x[id]);
                st.push(MP(nw, tp ^ 1));

                used[id] = tt;
                col[id] = (ite << deep);

                ite ^= 1;
                break;
            }

            if (!was) st.pop();
        }
    }

    vector<int> A, B;
    A.clear();
    B.clear();

    for (int cr : edges)
        if (col[cr] & (1 << deep))
            A.PB(cr);
        else B.PB(cr);

    deep++;
    calc(A);
    calc(B);
    deep--;
}

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

    cin >> l >> r >> m;

    n = max(l, r);

    vector<int> edges;
    edges.clear();

    for (int i = 0; i < m; i++){
        cin >> x[i] >> y[i];
        x[i]--; y[i]--;
        edges.PB(i);
    }

    calc(edges);

    int mx = 0;

    for (int i = 0; i < m; i++)
        mx = max(mx, col[i]);

    cout << mx + 1 << '\n';

    for (int i = 0; i < m; i++)
        cout << col[i] + 1 << '\n';

    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13