Submission #348549

#	Time	Username	Problem	Language	Result	Execution time	Memory
348549		arnold518	Link (CEOI06_link)	C++14	100 / 100	720 ms	87208 KiB

link

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;

int N, K;
int A[MAXN+10];
vector<int> adj[MAXN+10];
int deg[MAXN+10];
int col[MAXN+10];

int vis[MAXN+10], cyc[MAXN+10];
int dep[MAXN+10];
vector<int> V[MAXN+10];

void dfs(int now, int bef, int d)
{
	dep[now]=d;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(cyc[nxt]) continue;
		dfs(nxt, now, d+1);
	}
}

int par[MAXN+10][30];

int main()
{
	scanf("%d%d", &N, &K);
	for(int i=1; i<=N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		A[u]=v;
		adj[v].push_back(u);
		deg[v]++;
	}

	for(int i=1; i<=N; i++)
	{
		if(vis[i]) continue;

		int now=i;	
		vector<int> S;
		while(1)
		{
			vis[now]=i;
			S.push_back(now);
			if(vis[A[now]])
			{	
				if(vis[A[now]]!=i) break;
				while(!S.empty() && S.back()!=A[now])
				{
					V[i].push_back(S.back());
					cyc[S.back()]=i;
					S.pop_back();
				}
				V[i].push_back(A[now]);
				cyc[A[now]]=i;
				break;
			}
			now=A[now];
		}
	}
	for(int i=1; i<=N; i++) if(cyc[i])
	{
		dfs(i, i, 1);
	}
	//for(int i=1; i<=N; i++) printf("%d ", dep[i]); printf("\n");

	priority_queue<pii> PQ;

	int now=1;
	for(int i=1; i<=K+1; i++)
	{
		if(col[now]==0)
		{
			deg[A[now]]--;
		}
		col[now]=1;
		now=A[now];
	}

	for(int i=1; i<=N; i++) if(deg[i]==0 && col[i]==0 && !cyc[i]) PQ.push({dep[i], i});

	int ans=0;
	while(!PQ.empty())
	{
		int now=PQ.top().second; PQ.pop();
		if(deg[now]!=0) continue;
		if(col[now]) continue;
		if(cyc[now]) continue;
		ans++;
		//printf("%d\n", now);

		int u=now;
		for(int i=1; i<=K; i++)
		{
			if(col[u]==0)
			{
				deg[A[u]]--;
				if(!cyc[A[u]] && deg[A[u]]==0 && !col[A[u]]) PQ.push({dep[A[u]], A[u]});
			}
			col[u]=1;
			u=A[u];
		}
	}

	for(int i=1; i<=N; i++) if(!cyc[i]) assert(col[i]);

	for(int i=1; i<=N; i++)
	{
		if(V[i].empty()) continue;

		int L=V[i].size();
		vector<int> VV;
		for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j);
		for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L);
		for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L+L);
		if(VV.empty()) continue;
		if(K>=L)
		{
			ans++;
			continue;
		}

		int S=VV.size()/3;
		for(int i=0; i<S+S; i++) par[i][0]=lower_bound(VV.begin(), VV.end(), VV[i]+K)-VV.begin();
		for(int i=S+S; i<S+S+S; i++) par[i][0]=-1;
		for(int i=1; i<=20; i++) for(int j=0; j<S+S+S; j++)
		{
			if(par[j][i-1]==-1) par[j][i]=-1;
			else par[j][i]=par[par[j][i-1]][i-1];
		}

		int nans=987654321;
		for(int i=0; i<S; i++)
		{
			int now=i, val=1;
			for(int j=20; j>=0; j--)
			{
				if(par[now][j]!=-1 && VV[par[now][j]]<VV[i]+L)
				{
					now=par[now][j];
					val+=(1<<j);
				}
			}
			nans=min(nans, val);
		}
		ans+=nans;
	}

	//for(int i=1; i<=N; i++) assert(col[i]);
	printf("%d\n", ans);
}

Compilation message (stderr)

link.cpp: In function 'int main()':
link.cpp:123:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j);
      |                ~^~~~~~~~~~~~
link.cpp:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L);
      |                ~^~~~~~~~~~~~
link.cpp:125:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L+L);
      |                ~^~~~~~~~~~~~
link.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
link.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100