oj.uz

답안 #348549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348549 2021-01-15T07:44:38 Z arnold518 Link (CEOI06_link) C++14
100 / 100
 720 ms 87208 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23916 KB Output is correct
2 Correct 14 ms 23916 KB Output is correct
3 Correct 15 ms 23916 KB Output is correct
4 Correct 16 ms 24172 KB Output is correct
5 Correct 17 ms 24172 KB Output is correct
6 Correct 33 ms 27884 KB Output is correct
7 Correct 45 ms 28520 KB Output is correct
8 Correct 63 ms 31856 KB Output is correct
9 Correct 102 ms 42772 KB Output is correct
10 Correct 97 ms 38412 KB Output is correct
11 Correct 226 ms 81320 KB Output is correct
12 Correct 191 ms 37636 KB Output is correct
13 Correct 285 ms 57948 KB Output is correct
14 Correct 348 ms 59232 KB Output is correct
15 Correct 472 ms 73524 KB Output is correct
16 Correct 510 ms 80240 KB Output is correct
17 Correct 628 ms 82440 KB Output is correct
18 Correct 682 ms 69948 KB Output is correct
19 Correct 665 ms 74024 KB Output is correct
20 Correct 665 ms 78132 KB Output is correct
21 Correct 677 ms 87208 KB Output is correct
22 Correct 679 ms 86324 KB Output is correct
23 Correct 655 ms 86224 KB Output is correct
24 Correct 720 ms 86088 KB Output is correct
25 Correct 691 ms 85484 KB Output is correct