Submission #71440

#	Time	Username	Problem	Language	Result	Execution time	Memory
71440		zscoder	Rope (JOI17_rope)	C++17	100 / 100	2302 ms	167352 KiB

rope

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[1111111];
int ans[1111111];
int n,m; 
vi adj[1111111];
map<int,int> ma;
int sc[1111111];

void del(int x)
{
	ma[x]--; 
	if(!ma[x]) ma.erase(x);
}

void add(int x)
{
	ma[x]++;
}

void change(int id, int y)
{
	del(sc[id]); 
	sc[id]=y;
	add(sc[id]);
}

int getmx()
{
	if(ma.empty()) return -int(1e9);
	return (*prev(ma.end())).fi;
}

int sum[1111111];
int ct[1111111];
void solve(vector<int> &vec, vector<int> &extra)
{
	assert(int(vec.size())%2==0);
	vector<ii> pairs;
	memset(ct,0,sizeof(ct));
	for(int i=0;i<vec.size();i+=2)
	{
		if(vec[i]!=vec[i+1]) pairs.pb(mp(vec[i],vec[i+1]));
		else ct[vec[i]]++;
	}
	for(int i=0;i<m;i++) adj[i].clear();
	for(ii x:pairs)
	{
		adj[x.fi].pb(x.se); adj[x.se].pb(x.fi);
	}
	ma.clear();
	for(int i=0;i<m;i++)
	{
		int res=2*ct[i];
		for(int x:extra)
		{
			if(x==i) res++;
		}
		res+=adj[i].size();
		sc[i]=res; add(res);
	}
	for(int i=0;i<m;i++)
	{
		del(sc[i]); int deg=adj[i].size();
		int t=0;
		for(int v:extra)
		{
			if(v==i) t++;
		}
		vi V;
		for(int v:adj[i])
		{
			sum[v]++;
			if(sum[v]==1) V.pb(v);
		}
		vi ori;
		for(int v:V)
		{
			ori.pb(sc[v]);
			change(v, sc[v] - sum[v]);
		}
		ans[i] = min(ans[i], n - (2*ct[i] + getmx() + deg + t));
		int ptr=0;
		for(int v:V)
		{
			change(v,ori[ptr++]);
		}
		for(int v:adj[i])
		{
			sum[v]--;
		}
		add(sc[i]);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++) ans[i]=int(1e9);
	vector<int> cnt(m,0);
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; a[i]--; cnt[a[i]]++; 
	}
	for(int i=0;i<m;i++) ans[i]=n-cnt[i];
	if(n%2==0)
	{
		vi tmp; vi emp;
		for(int i=0;i<n;i++) tmp.pb(a[i]);
		solve(tmp,emp);
		vi extra;
		extra.pb(a[0]); extra.pb(a[n-1]);
		vi serious;
		for(int i=1;i<n-1;i++) serious.pb(a[i]);
		solve(serious,extra);
	}
	else
	{
		for(int z=0;z<2;z++)
		{
			vi extra;
			extra.pb(a[n-1]);
			vi serious;
			for(int i=0;i<n-1;i++) serious.pb(a[i]);
			solve(serious,extra);
			reverse(a,a+n);
		}
	}
	for(int i=0;i<m;i++)
	{
		cout<<ans[i]<<'\n';
	}
}	

Compilation message (stderr)

rope.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&)':
rope.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i+=2)
              ~^~~~~~~~~~~

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