oj.uz

Submission #92785

# Submission time Handle Problem Language Result Execution time Memory
92785 2019-01-04T13:56:57 Z Kastanda Teoretičar (COCI18_teoreticar) C++11
130 / 130
 4885 ms 60168 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;
            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

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

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 5 ms 5012 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 5 ms 5108 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5748 KB Output is correct
2 Correct 10 ms 5624 KB Output is correct
3 Correct 13 ms 5880 KB Output is correct
4 Correct 8 ms 5512 KB Output is correct
5 Correct 8 ms 5368 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5624 KB Output is correct
2 Correct 9 ms 5624 KB Output is correct
3 Correct 12 ms 6136 KB Output is correct
4 Correct 8 ms 5496 KB Output is correct
5 Correct 7 ms 5368 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 37188 KB Output is correct
2 Correct 4014 ms 60044 KB Output is correct
3 Correct 1243 ms 59480 KB Output is correct
4 Correct 627 ms 43040 KB Output is correct
5 Correct 385 ms 34292 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 37176 KB Output is correct
2 Correct 1335 ms 59356 KB Output is correct
3 Correct 2573 ms 58076 KB Output is correct
4 Correct 639 ms 43064 KB Output is correct
5 Correct 127 ms 14184 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2320 ms 48552 KB Output is correct
2 Correct 3346 ms 60004 KB Output is correct
3 Correct 107 ms 12656 KB Output is correct
4 Correct 732 ms 43552 KB Output is correct
5 Correct 181 ms 25480 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 45276 KB Output is correct
2 Correct 4885 ms 59940 KB Output is correct
3 Correct 3237 ms 58984 KB Output is correct
4 Correct 1077 ms 48000 KB Output is correct
5 Correct 671 ms 42992 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 815 ms 36960 KB Output is correct
2 Correct 4469 ms 59944 KB Output is correct
3 Correct 3084 ms 60168 KB Output is correct
4 Correct 621 ms 47964 KB Output is correct
5 Correct 716 ms 42972 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 37024 KB Output is correct
2 Correct 4179 ms 59876 KB Output is correct
3 Correct 3632 ms 60036 KB Output is correct
4 Correct 156 ms 15476 KB Output is correct
5 Correct 812 ms 43488 KB Output is correct