Submission #253612

#	Time	Username	Problem	Language	Result	Execution time	Memory
253612		Tuk1352	Rope (JOI17_rope)	C++11	100 / 100	1327 ms	92408 KiB

rope

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n], K[n+1], K1[n+1], KY[n+1], G[n+1], Re[m+1], Ma=0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        K[i] = 0;
        KY[i] = 0;
    }
    K[n] = 0;
    KY[n] = 0;
    vector <int> V[n+1], Ch;
    for (int i = 0; i < n; i += 2)
    {
        if (i == n-1)
        {
            K[a[i]]++;
        }
        else
        {
            K[a[i]]++;
            K[a[i+1]]++;
            if (a[i] != a[i+1])
            {
                V[a[i]].push_back(a[i+1]);
                V[a[i+1]].push_back(a[i]);
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        K1[i] = K[i];
        KY[K[i]]++;
        G[i] = 1;
        Ma = max(Ma, K[i]);
    }

    for (int i = 1; i <= m; i++)
    {
        Re[i] = 0;
        G[i] = 0;
        Ch.push_back(i);
        KY[K[i]]--;
        KY[0]++;
        K1[i] = 0;
        while (KY[Ma] == 0)
        {
            Ma--;
        }
        for (int y = 0; y < V[i].size(); y++)
        {
            int A = V[i][y];
            KY[K1[A]]--;
            K1[A]--;
            KY[K1[A]]++;
            while (KY[Ma] == 0)
            {
                Ma--;
            }
            if (G[A] == 1)
            {
                G[A] = 0;
                Ch.push_back(A);
            }
        }
        Re[i] = n - Ma - K[i];
        for (int y = 0; y < Ch.size(); y++)
        {
            int A = Ch[y];
            G[A] = 1;
            KY[K1[A]]--;
            KY[K[A]]++;
            K1[A] = K[A];
            Ma = max(Ma, K[A]);
        }
        Ch.clear();
    }
    for (int i = 0; i <= n; i++)
    {
        V[i].clear();
        K[i] = 0;
        KY[i] = 0;
    } //

    K[a[0]]++;
    for (int i = 1; i < n; i += 2)
    {
        if (i == n-1)
        {
            K[a[i]]++;
        }
        else
        {
            K[a[i]]++;
            K[a[i+1]]++;
            if (a[i] != a[i+1])
            {
                V[a[i]].push_back(a[i+1]);
                V[a[i+1]].push_back(a[i]);
            }
        }
    }
    for (int i = 1; i <= m; i++)
    {
        K1[i] = K[i];
        KY[K[i]]++;
        G[i] = 1;
        Ma = max(Ma, K[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        G[i] = 0;
        Ch.push_back(i);
        KY[K[i]]--;
        K1[i] = 0;
        KY[0]++;
        while (KY[Ma] == 0)
        {
            Ma--;
        }
        for (int y = 0; y < V[i].size(); y++)
        {
            int A = V[i][y];
            KY[K1[A]]--;
            K1[A]--;
            KY[K1[A]]++;
            if (KY[Ma] == 0)
            {
                Ma--;
            }
            if (G[A] == 1)
            {
                G[A] = 0;
                Ch.push_back(A);
            }
        }
        Re[i] = min(n - Ma - K[i], Re[i]);
        for (int y = 0; y < Ch.size(); y++)
        {
            int A = Ch[y];
            G[A] = 1;
            KY[K1[A]]--;
            KY[K[A]]++;
            K1[A] = K[A];
            Ma = max(Ma, K[A]);
        }
        Ch.clear();
    }
    for (int i = 1; i <= m; i++)
    {
        cout << Re[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:55:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int y = 0; y < V[i].size(); y++)
                         ~~^~~~~~~~~~~~~
rope.cpp:72:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int y = 0; y < Ch.size(); y++)
                         ~~^~~~~~~~~~~
rope.cpp:126:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int y = 0; y < V[i].size(); y++)
                         ~~^~~~~~~~~~~~~
rope.cpp:143:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int y = 0; y < Ch.size(); y++)
                         ~~^~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20