oj.uz

Submission #92780

# Submission time Handle Problem Language Result Execution time Memory
92780 2019-01-04T13:50:35 Z Kastanda Teoretičar (COCI18_teoreticar) C++11
0 / 130
 2487 ms 52732 KB 
#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;
        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

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:86: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:89: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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4984 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5756 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 5740 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1233 ms 43620 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1219 ms 43640 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2487 ms 52732 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1227 ms 49416 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 937 ms 40052 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 933 ms 40148 KB too many colors
2 Halted 0 ms 0 KB -