Submission #51002

#	Time	Username	Problem	Language	Result	Execution time	Memory
51002		Diuven	Rope (JOI17_rope)	C++11	100 / 100	1652 ms	81856 KiB

rope

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MX=1000010, inf=2e9;

int n, m, A[MX];
int C[MX];
int ans[MX];
int idx[MX];

vector<int> G[MX];

void init(int st){
    for(int i=1; i<=m; i++)
        G[i].clear(), C[i]=0;
    for(int i=st; i<=n; i+=2){
        C[A[i]]++; C[A[i+1]]++;
    }
    C[0]=0;
    for(int i=st; i<n; i+=2){
        if(i<1 || A[i]==A[i+1]) continue;
        G[A[i]].push_back(A[i+1]);
        G[A[i+1]].push_back(A[i]);
    }
    iota(idx+1, idx+m+1, 1);
    sort(idx+1, idx+m+1, [](int a, int b){ return C[a]>C[b]; });
}

void solve(int st){
    init(st);
    int adj[MX]={};

    for(int v=1; v<=m; v++){
        int mx=0;
        for(int x:G[v]) adj[x]++;
        for(int x:G[v]){
            mx=max(mx, C[x]-adj[x]);
        }
        for(int i=1; i<=m; i++){
            int x=idx[i];
            if(x!=v && adj[x]==0){
                mx=max(mx, C[x]);
                break;
            }
        }
        for(int x:G[v]) adj[x]--;
        ans[v]=min(ans[v], n-C[v]-mx);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>A[i];
    fill(ans+1, ans+m+1, inf);

    solve(0);
    solve(1);
    
    for(int i=1; i<=m; i++) cout<<ans[i]<<'\n';

    return 0;
}

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