Submission #92785

#	Time	Username	Problem	Language	Result	Execution time	Memory
92785		Kastanda	Teoretičar (COCI18_teoreticar)	C++11	130 / 130	4885 ms	60168 KiB

teoreticar

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int VR = 100005, N = VR * 7;
int n1, n2, m, ts, parity;
int A[N], B[N], C[N], P[N], M[N];
vector < int > Adj[VR * 2];
void DFS(int v)
{
    while (Adj[v].size())
    {
        int id = Adj[v].back();
        Adj[v].pop_back();
        if (M[id]) continue;
        M[id] = parity;
        parity = - parity;
        DFS(A[id] ^ B[id] ^ v);
    }
}
void Solve(int l, int r)
{
    int Mxd = 0;
    if (r < l) return ;
    for (int i = l; i <= r; i++)
    {
        Adj[A[P[i]]].pb(P[i]);
        Adj[B[P[i]]].pb(P[i]);
        Mxd = max({Mxd, (int)Adj[A[P[i]]].size(), (int)Adj[B[P[i]]].size()});
    }
    if (Mxd <= 1)
    {
        ++ ts;
        for (int i = l; i <= r; i++)
        {
            C[P[i]] = ts;
            Adj[A[P[i]]].clear();
            Adj[B[P[i]]].clear();
        }
        return ;
    }
    int _m = m; parity = 1;
    int dum1 = n1 + n2 + 1, dum2 = dum1 + 1;
    vector < int > V;
    for (int i = l; i <= r; i++)
    {
        int v = A[P[i]], u = B[P[i]];
        V.pb(v); V.pb(u);
        if (Adj[v].size() & 1)
        {
            ++ _m;
            A[_m] = v;
            B[_m] = dum2;
            Adj[v].pb(_m);
            Adj[dum2].pb(_m);
        }
        if (Adj[u].size() & 1)
        {
            ++ _m;
            A[_m] = dum1;
            B[_m] = u;
            Adj[dum1].pb(_m);
            Adj[u].pb(_m);
        }
    }
    V.pb(dum1); V.pb(dum2);
    if (Adj[dum1].size() & 1)
    {
        ++ _m;
        A[_m] = dum1;
        B[_m] = dum2;
        Adj[dum1].pb(_m);
        Adj[dum2].pb(_m);
    }
    for (int &v : V)
        if (Adj[v].size())
            DFS(v);
    int nw = l;
    for (int i = l; i <= r; i++)
        if (M[P[i]] == 1)
            swap(P[i], P[nw]), nw ++;
    for (int i = l; i <= r; i++)
        M[P[i]] = 0;
    for (int i = m + 1; i <= _m; i++)
        M[i] = 0;
    Solve(l, nw - 1);
    Solve(nw, r);
}
int main()
{
    scanf("%d%d%d", &n1, &n2, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &A[i], &B[i]),
        B[i] += n1, P[i] = i;
    Solve(1, m);
    printf("%d\n", ts);
    for (int i = 1; i <= m; i++)
        printf("%d\n", C[i]);
    return (0);
}

Compilation message (stderr)

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n1, &n2, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:93:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &A[i], &B[i]),
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         B[i] += n1, P[i] = i;
         ~~~~~~~~~~^~~~~~~~~~

• 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