Submission #136202

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136202	2019-07-25T01:05:17 Z	gs14004	Link (CEOI06_link)	C++17	100 / 100	462 ms	38136 KB

link

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int nxt[500005];
int ind[500005];
int paint[500005];
int vis[500005];
int n, k;

queue<int> q;
vector<int> graph[500005];

int cnt = 0;

int dfs(int x){
	int ret = 0;
	if(x == 1) ret = k;
	for(auto &i : graph[x]){
		ret = max(ret, dfs(i));
	}
	ret--;
	if(ret < 0) ret = k-1, cnt++; 
	return ret;
}

int col[500005], jmp[500005];

void solve_cycle(int x){
	int p = 0;
	while(!vis[x]){
		vis[x] = 1;
		col[p++] = paint[x];
		x = nxt[x];
	}
	int pcol = col[0];
	for(int i=1; i<2*p; i++){
		pcol = col[i%p] = max(pcol - 1, col[i%p]);
	}
	for(int i=p; i>=0; i--){
		if(!col[i]) jmp[i] = i;
		else jmp[i] = jmp[i+1];
	}
	int tcnt = 0;
	int pos = jmp[0];
	while(pos < p){
		pos = jmp[min(pos + k, p)];
		tcnt++;
	}
	for(int i=1; i<min(k,p); i++){
		int q = p-k+i;
		int pos = jmp[i];
		int cnt = 0;
		while(pos < q){
			pos = jmp[min(pos + k, p)];
			cnt++;
		}
		tcnt = min(tcnt, cnt + 1);
	}
	cnt += tcnt;
	memset(col, 0, sizeof(int) * (2*p+1));
	memset(jmp, 0, sizeof(int) * (p+1));
}

int main(){
	scanf("%d %d",&n,&k);
	for(int i=1; i<=n; i++){
		int x;
		scanf("%d",&x);
		scanf("%d",&nxt[x]);
		ind[nxt[x]]++;
		graph[nxt[x]].push_back(x);
	}
	for(int i=1; i<=n; i++){
		if(ind[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int qf = q.front();
		q.pop();
		vis[qf] = 1;
		ind[nxt[qf]]--;
		if(ind[nxt[qf]] == 0){
			q.push(nxt[qf]);
		}
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			int ret = -1;
			for(int j=0; j<graph[i].size(); j++){
				if(!vis[graph[i][j]]) continue;
				ret = max(ret, dfs(graph[i][j]) - 1);
			}
			paint[i] = ret + 1; // who will paint me
			if(i == 1) paint[i] = k + 1;
		}
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			solve_cycle(i);
		}
	}
	printf("%d",cnt);
}

Compilation message

link.cpp: In function 'int main()':
link.cpp:110:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0; j<graph[i].size(); j++){
                 ~^~~~~~~~~~~~~~~~
link.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
link.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
link.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&nxt[x]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	12152 KB	Output is correct
2	Correct	12 ms	12152 KB	Output is correct
3	Correct	13 ms	12152 KB	Output is correct
4	Correct	14 ms	12280 KB	Output is correct
5	Correct	15 ms	12324 KB	Output is correct
6	Correct	28 ms	13556 KB	Output is correct
7	Correct	40 ms	14612 KB	Output is correct
8	Correct	52 ms	15608 KB	Output is correct
9	Correct	77 ms	18260 KB	Output is correct
10	Correct	78 ms	17144 KB	Output is correct
11	Correct	113 ms	21368 KB	Output is correct
12	Correct	166 ms	21496 KB	Output is correct
13	Correct	211 ms	25976 KB	Output is correct
14	Correct	269 ms	26896 KB	Output is correct
15	Correct	296 ms	30304 KB	Output is correct
16	Correct	371 ms	32004 KB	Output is correct
17	Correct	397 ms	34808 KB	Output is correct
18	Correct	456 ms	36264 KB	Output is correct
19	Correct	444 ms	36644 KB	Output is correct
20	Correct	430 ms	37260 KB	Output is correct
21	Correct	427 ms	38136 KB	Output is correct
22	Correct	460 ms	37496 KB	Output is correct
23	Correct	462 ms	37428 KB	Output is correct
24	Correct	422 ms	37420 KB	Output is correct
25	Correct	417 ms	37040 KB	Output is correct