Submission #535579

#	Time	Username	Problem	Language	Result	Execution time	Memory
535579		amunduzbaev	Rope (JOI17_rope)	C++17	100 / 100	1862 ms	123680 KiB

rope

#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 1e6 + 5;
int a[N], res[N], cc[N];
map<int, int> edges[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]--;
		cc[a[i]]++;
	}
	vector<int> tot(m); iota(tot.begin(), tot.end(), 0);
	sort(tot.begin(), tot.end(), [&](int i, int j){
		if(cc[i] != cc[j]) return cc[i] > cc[j];
		return i > j;
	});
	
	{
		for(int i=1;i+1<n;i+=2){
			edges[a[i]][a[i+1]]++;
			edges[a[i+1]][a[i]]++;
		} 
		for(int i=0;i<m;i++){
			int rr = 0;
			edges[i][i] = cc[i];
			vector<ar<int, 2>> t;
			for(auto x : edges[i]){
				t.push_back({x.first, x.second});
			}
			
			sort(t.begin(), t.end(), [&](auto& a, auto& b){
				if(cc[a[0]] != cc[b[0]]) return cc[a[0]] > cc[b[0]];
				return a[0] > b[0];
			});
			
			int l = 0;
			for(auto x : t){
				if(tot[l] == x[0]) l++;
				rr = max(rr, cc[x[0]] - x[1]);
			}
			
			if(l < m) rr = max(rr, cc[tot[l]]);
			res[i] = max(res[i], rr + cc[i]);
			edges[i].clear();
		}
	}


	{
		for(int i=0;i+1<n;i+=2){
			edges[a[i]][a[i+1]]++;
			edges[a[i+1]][a[i]]++;
		} 
		for(int i=0;i<m;i++){
			int rr = 0;
			edges[i][i] = cc[i];
			vector<ar<int, 2>> t;
			for(auto x : edges[i]){
				t.push_back({x.first, x.second});
			}
			
			sort(t.begin(), t.end(), [&](auto& a, auto& b){
				if(cc[a[0]] != cc[b[0]]) return cc[a[0]] > cc[b[0]];
				return a[0] > b[0];
			});
			
			int l = 0;
			for(auto x : t){
				if(tot[l] == x[0]) l++;
				rr = max(rr, cc[x[0]] - x[1]);
			}
			
			if(l < m) rr = max(rr, cc[tot[l]]);
			res[i] = max(res[i], rr + cc[i]);
			edges[i].clear();
		}
	}
	
	for(int i=0;i<m;i++) cout<<n - res[i]<<"\n";
}

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