Submission #232572

#	Time	Username	Problem	Language	Result	Execution time	Memory
232572		TempoTemp	Trapezi (COI17_trapezi)	C++14	63 / 100	370 ms	508 KiB

trapezi

// Pied!
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 155, K = 20;
int n, k, ts, rev[K][K], P[N], M[N], C[N], dp[N][3];
string S[N], T[N];
vector < int > Adj[N], Ad[N];
vector < pair < int , int > > E;
mt19937 Rnd;
inline void AddEdge(int v, int u){E.pb({u, v});}
int Find(int v) {return P[v] < 0 ? v : (P[v] = Find(P[v]));}
inline void SpanningTree()
{
    for (int i = 0; i <= n; i ++)
        Adj[i].clear();
    shuffle(E.begin(), E.end(), Rnd);
    memset(P, -1, sizeof(P));

    for (auto X : E)
    {
        int v = Find(X.first);
        int u = Find(X.second);
        if (v == u)
            continue;
        Adj[X.first].pb(X.second);
        Adj[X.second].pb(X.first);
        P[v] = u;
    }
}
void DFS(int v)
{
    M[v] = 1;
    dp[v][1] = 0;
    dp[v][0] = dp[v][2] = -N;
    for (int u : Adj[v])
        if (!M[u])
        {
            DFS(u);
            int dpt[3] = {-N, -N, -N};
            for (int w = 0; w < 3; w ++)
                dpt[w] = max(dp[v][w], dp[v][w] + dp[u][0]);
            dpt[2] = max(dpt[2], dp[v][1] + dp[u][1]);
            dpt[0] = max(dpt[0], dp[v][2] + dp[u][1] + 1);
            dpt[0] = max(dpt[0], dp[v][1] + dp[u][2] + 1);
            for (int w = 0; w < 3; w ++)
                dp[v][w] = max(dp[v][w], dpt[w]);

        }
}
void Build(int v, int c, int cl)
{
    M[v] = cl;
    if (c == 1)
    {
        for (int u : Adj[v])
            if (!M[u]) Build(u, 0, ++ ts);
        return ;
    }
    if (c == 2)
    {
        int SM = 0, opt = -1;
        for (int u : Adj[v])
            if (!M[u]) SM += dp[u][0];
        for (int u : Adj[v])
            if (!M[u] && dp[v][2] == SM - dp[u][0] + dp[u][1])
                opt = u;
        Build(opt, 1, cl);
        for (int u : Adj[v])
            if (!M[u])
                Build(u, 0, ++ ts);
        return ;
    }
    if (c == 0)
    {
        int SM = 0;
        for (int u : Adj[v])
            if (!M[u])
                SM += dp[u][0];
        int opt1 = -1, opt2 = -1;
        for (int u1 : Adj[v])
            if (!M[u1])
                for (int u2 : Adj[v])
                    if (!M[u2] && u1 < u2)
                        if (dp[v][0] == SM - dp[u1][0] - dp[u2][0] + dp[u1][1] + dp[u2][1] + 1)
                            opt1 = u1, opt2 = u2;
        if (opt1 != -1)
        {
            Build(opt1, 1, cl);
            Build(opt2, 1, cl);
            for (int u : Adj[v])
                if (!M[u])
                    Build(u, 0, ++ ts);
            return ;
        }
        for (int u : Adj[v])
            if (!M[u] && dp[v][0] == SM - dp[u][0] + dp[u][2] + 1)
                opt1 = u;
        assert(opt1 != -1);
        Build(opt1, 2, cl);
        for (int u : Adj[v])
            if (!M[u])
                Build(u, 0, ++ ts);
        return ;
    }
}
void Recolor(int v)
{
    vector < int > Mark(7, 0);
    for (int u : Ad[v])
        Mark[C[u]] = 1;
    C[v] = 1;
    while (Mark[C[v]])
        C[v] ++;
    for (int u : Ad[v])
        if (!C[u]) Recolor(u);
}
inline bool Try()
{
    SpanningTree();
    memset(M, 0, sizeof(M));
    iota(P, P + n + 1, 0);
    //shuffle(P + 1, P + n + 1, Rnd);
    vector < int > rts;
    memset(M, 0, sizeof(M));
    for (int j = 1; j <= n; j ++)
        if (!M[P[j]])
            DFS(P[j]), rts.push_back(P[j]);

    int SM = 0;
    for (int r : rts)
        SM += dp[r][0];
    if (SM != n / 3)
        return 0;

    memset(M, 0, sizeof(M));
    for (int r : rts)
        Build(r, 0, ++ ts);

    for (auto X : E)
    {
        int v = X.first;
        int u = X.second;
        if (M[v] != M[u])
            Ad[M[v]].pb(M[u]),
            Ad[M[u]].pb(M[v]);
    }

    for (int i = 1; i <= ts; i ++)
        if (!C[i])
            Recolor(i);

    int cnt = 0;
    for (int i = 1; i <= k + k; i ++)
    {
        T[i] = S[i];
        for (int j = 0; j < (int)S[i].size(); j ++)
            if (S[i][j] == '0')
                T[i][j] = '0' + C[M[++ cnt]];
    }

    for (int i = 1; i <= k + k; i ++)
        cout << T[i] << "\n";
    exit(0);
}
inline void Solve(int TF)
{
    for (int __ = 0; __ < TF; __ ++)
        Try();
    printf("nemoguce\n");
    return ;
}
int main()
{
    Rnd = mt19937(time(0));
    cin >> k;
    for (int i = 1; i <= k + k; i ++)
    {
        cin >> S[i];
        for (int j = 0; j < (int)S[i].size(); j ++)
            if (S[i][j] == '0')
                rev[i][j] = ++ n;
        for (int j = 1; j < (int)S[i].size(); j ++)
            if (S[i][j] == '0' && S[i][j - 1] == '0')
                AddEdge(rev[i][j], rev[i][j - 1]);
    }
    if (n % 3 != 0)
        return !printf("nemoguce\n");
    for (int i = 1; i < k; i ++)
        for (int j = 0; j < (int)S[i].size(); j += 2)
            if (S[i][j] == '0' && S[i + 1][j + 1] == '0')
                AddEdge(rev[i][j], rev[i + 1][j + 1]);
    for (int j = 0; j < (int)S[k].size(); j += 2)
        if (S[k][j] == '0' && S[k + 1][j] == '0')
            AddEdge(rev[k][j], rev[k + 1][j]);
    for (int i = k + k; i > k + 1; i --)
        for (int j = 0; j < (int)S[i].size(); j += 2)
            if (S[i][j] == '0' && S[i - 1][j + 1] == '0')
                AddEdge(rev[i][j], rev[i - 1][j + 1]);

    int TF = 5e4;
    if (k == 5)
        TF = 25e3;
    Solve(TF);
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 22 / 22
• Subtask 5: 0 / 37