fork download
copy 
  1. #include <cmath>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 12345
  13. #define MAX 1037471823
  14. #define Q 103
  15.  
  16. using namespace std;
  17.  
  18. int n, m, k[MS], r[MS], l[MS], next[MS], last[MS], h[MS], s[MS], a, now;
  19. bool b[MS];
  20. struct node
  21. {
  22. 	int x, y;
  23. 	bool operator < (const node &k) const { return x < k.x || (x == k.x && y < k.y); }
  24. } c[2345678];
  25.  
  26. int main()
  27. {
  28. 	scanf("%d%d", &n, &m);
  29. 	rep(i, 1, m) scanf("%d%d", &c[i].x, &c[i].y);
  30. 	rep(i, 1, m) c[i+m].x = c[i].y, c[i+m].y = c[i].x; m *= 2;
  31. 	sort(c+1, c+1+m); c[m+1].x = MAX;
  32. 	rep(i, 2, m) if (c[i].x == c[i-1].x && c[i].y == c[i-1].y) c[i] = c[m+1];
  33. 	sort(c+1, c+1+m); while (c[m].x == MAX) m--;
  34. 	k[1] = 1; rep(i, 2, n+1) { k[i] = k[i-1]; while (c[k[i]].x < i) k[i]++; }
  35.  
  36. 	h[0] = n; rep(i, 2, n) next[i] = i-1; rep(i, 1, n-1) last[i] = i+1; now = 0;
  37. 	down(i, n, 1)
  38. 	{
  39. 		l[i] = h[now]; b[l[i]] = true; h[now] = next[h[now]]; if (h[now] != 0) last[h[now]] = 0;
  40. 		while (h[now] == 0 && now > 0) now--;
  41. 		rep(j, k[l[i]], k[l[i]+1]-1) if (b[c[j].y] == false) 
  42. 		{
  43. 			a = c[j].y;
  44. 			if (a != h[r[a]]) next[last[a]] = next[a], last[next[a]] = last[a]; else h[r[a]] = next[a], last[next[a]] = 0;
  45. 			r[a]++; 
  46. 			if (r[a] > now) now = r[a];
  47. 			next[a] = h[r[a]]; last[h[r[a]]] = a; h[r[a]] = a; last[a] = 0;
  48. 		}
  49. 	}
  50.  
  51. 	now = 0;
  52. 	down(i, n, 1) 
  53. 	{
  54. 		rep(j, 1, now) b[j] = false;
  55. 		rep(j, k[l[i]], k[l[i]+1]-1) b[s[c[j].y]] = true; 
  56. 		a = 0;
  57. 		down(j, now, 1) if (b[j] == false) a = j;
  58. 		if (a == 0) now++, s[l[i]] = now; else s[l[i]] = a;
  59. 	}
  60. 	printf("%d\n", now);
  61. 	return 0;
  62. }
  63.  
Success #stdin #stdout 0s 22024KB
comments (?)
stdin
copy 
4 5
1 2
1 4
2 4
2 3
3 4
stdout
copy 
3
https://ideone.com/xbnW4N
BZOJ 1006
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!