제출 #1180450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180450		Szymon_Pilipczuk	Rope (JOI17_rope)	C++20	0 / 100	0 ms	328 KiB

rope

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define st first
#define nd second
#define all(a) a.begin(),a.end()
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> c(n);
    vector<int> am(m);
    vector<unordered_set<int>> s(m);
    vector<unordered_set<int>> s2(m);
    vector<pair<int,int>> e;
    vector<pair<int,int>> e2;
    for(int i =0 ;i<n;i++)
    {
        cin>>c[i];
        c[i]--;
        am[c[i]]++;
    }
    if(m == 1)
    {
        cout<<0<<"\n";
        return 0;
    }
    vector<pair<int,int>> w;
    for(int i = 0;i<m;i++)
    {
        w.push_back({am[i],i});
    }
    sort(all(w));
    reverse(all(w));
    for(int i = 0;i<n;i++)
    {
        if(i < n-1)
        {
            if(c[i+1] != c[i])
            {
                if(i%2 == 0)
                {
                    e.push_back({c[i],c[i+1]});
                    e.push_back({c[i+1],c[i]});
                    s[c[i]].insert(c[i+1]);
                    s[c[i+1]].insert(c[i]);
                }
                else
                {
                    e2.push_back({c[i],c[i+1]});
                    e2.push_back({c[i+1],c[i]});
                    s2[c[i]].insert(c[i+1]);
                    s2[c[i+1]].insert(c[i]);
                }
            }
        }
    }
    vector<int> tans(m,1e9);
    for(int i = 0;i<m;i++)
    {
        for(int j = 0;j<m;j++)
        {
            if(s[i].find(w[j].nd) == s[i].end())
            {
                tans[i] = min(tans[i],n-am[w[j].nd]-am[i]);
            }
        }
    }
    for(int i = 0;i<m;i++)
    {
        for(int j = 0;j<m;j++)
        {
            if(s2[i].find(w[j].nd) == s2[i].end())
            {
                tans[i] = min(tans[i],n-am[w[j].nd]-am[i]);
            }
        }
    }

    sort(all(e));
    sort(all(e2));
    int i =0;
    while(i < e.size())
    {
        int j = i;
        int ans = 1e9;
        while(e[i].st == e[j].st)
        {
            int q = j;
            int value = 0;
            while(e[j].nd == e[q].nd && e[j].st == e[q].st)
            {
                value++;
                q++;
            }
            j = q;
            ans = min(ans,n-am[e[j].st]-am[e[j].nd]+value);
        }
        tans[e[i].st] = min(tans[e[i].st],ans);
        i = j;

    }
    i = 0;
    while(i < e2.size())
    {
        int j = i;
        int ans = 1e9;
        while(e2[i].st == e2[j].st)
        {
            int q = j;
            int value = 0;
            while(e2[j].nd == e2[q].nd && e2[j].st == e2[q].st)
            {
                value++;
                q++;
            }
            j = q;
            ans = min(ans,n-am[e2[j].st]-am[e2[j].nd]+value);
        }
        tans[e2[i].st] = min(tans[e2[i].st],ans);
        i = j;
    }

    for(int i =0 ;i<m;i++)
    {
        cout<<tans[i]<<"\n";
    }
}

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