제출 #228340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228340		VEGAnn	Teoretičar (COCI18_teoreticar)	C++14	130 / 130	4810 ms	44264 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: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13