Submission #228340

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
228340	2020-04-30T15:47:00 Z	VEGAnn	Teoretičar (COCI18_teoreticar)	C++14	130 / 130	4810 ms	44264 KB

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.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	7 ms	5120 KB	Output is correct
4	Correct	7 ms	5120 KB	Output is correct
5	Correct	7 ms	5120 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5120 KB	Output is correct
2	Correct	7 ms	5120 KB	Output is correct
3	Correct	9 ms	5120 KB	Output is correct
4	Correct	7 ms	5120 KB	Output is correct
5	Correct	8 ms	5120 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	5632 KB	Output is correct
2	Correct	12 ms	5504 KB	Output is correct
3	Correct	14 ms	5760 KB	Output is correct
4	Correct	9 ms	5376 KB	Output is correct
5	Correct	9 ms	5376 KB	Output is correct

Subtask #4
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	5504 KB	Output is correct
2	Correct	12 ms	5504 KB	Output is correct
3	Correct	14 ms	5760 KB	Output is correct
4	Correct	10 ms	5376 KB	Output is correct
5	Correct	9 ms	5248 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	682 ms	26028 KB	Output is correct
2	Correct	4402 ms	43524 KB	Output is correct
3	Correct	1370 ms	41708 KB	Output is correct
4	Correct	563 ms	30696 KB	Output is correct
5	Correct	389 ms	23016 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	675 ms	25708 KB	Output is correct
2	Correct	1391 ms	42100 KB	Output is correct
3	Correct	2483 ms	41448 KB	Output is correct
4	Correct	572 ms	30696 KB	Output is correct
5	Correct	95 ms	10356 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2422 ms	33476 KB	Output is correct
2	Correct	3307 ms	43240 KB	Output is correct
3	Correct	142 ms	12020 KB	Output is correct
4	Correct	635 ms	28228 KB	Output is correct
5	Correct	181 ms	23060 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	910 ms	27000 KB	Output is correct
2	Correct	4614 ms	44080 KB	Output is correct
3	Correct	2859 ms	40416 KB	Output is correct
4	Correct	741 ms	31720 KB	Output is correct
5	Correct	531 ms	30956 KB	Output is correct

Subtask #9
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	744 ms	21352 KB	Output is correct
2	Correct	4810 ms	44264 KB	Output is correct
3	Correct	3959 ms	43500 KB	Output is correct
4	Correct	692 ms	31896 KB	Output is correct
5	Correct	597 ms	27496 KB	Output is correct

Subtask #10
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	740 ms	21352 KB	Output is correct
2	Correct	4772 ms	42368 KB	Output is correct
3	Correct	2635 ms	43192 KB	Output is correct
4	Correct	122 ms	10992 KB	Output is correct
5	Correct	629 ms	25960 KB	Output is correct

Submission #228340

Compilation message