Guest User

Untitled

a guest
Oct 21st, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.62 KB | None | 0 0
  1. //2072 - The Flat Cupboard
  2. //Live Archive
  3.  
  4. /*
  5. Monte o grafo da seguinte forma: Se um item x precisa ser retirado para um item y sair, então existe uma aresta de x para y.
  6. Após isso faça uma DFS a partir do item que se deseja tirar contando quantos vértices são atingíveis a partir dele. Todo vértice
  7. atingível será um elemento que precisa ser retirado antes dele. O número de vértices atingíveis é a resposta.
  8. */
  9.  
  10. #include <cstdio>
  11. #include <map>
  12. #include <cstdlib>
  13. #include <cmath>
  14. #include <algorithm>
  15. #include <cstring>
  16. #include <string>
  17. #include <vector>
  18.  
  19. #define f(i,n) for(int i = 0; i < n; i++)
  20.  
  21. using namespace std;
  22.  
  23. struct obj{
  24. int xl, yl, xr, yr;
  25. int adj[110];
  26. int last;
  27. void add(int v){
  28. adj[last++] = v;
  29. }
  30.  
  31. //Verify if b is above this
  32. bool above(obj b){
  33. if(max(xl,b.xl) < min(xr,b.xr)) return yr <= b.yl;
  34. return false;
  35. }
  36.  
  37. bool operator == (const obj & b) const{
  38. return xr == b.xr && xl == b.xl && yr == b.yr && yl == b.yl;
  39. }
  40. } r[110];
  41.  
  42. int n;
  43.  
  44. bool read(){
  45. scanf("%d", &n);
  46. if(!n) return false;
  47.  
  48. f(i,n+1){
  49. r[i].last = 0;
  50. scanf("%d%d%d%d", &r[i].xl, &r[i].yl, &r[i].xr, &r[i].yr);
  51. }
  52.  
  53. return true;
  54. }
  55.  
  56. bool mark[110];
  57.  
  58. int dfs(int v){
  59. if(mark[v]) return 0;
  60. mark[v] = true;
  61.  
  62. int res = 1;
  63.  
  64. f(i,r[v].last){
  65. res += dfs(r[v].adj[i]);
  66. }
  67.  
  68. return res;
  69. }
  70.  
  71. void process(){
  72. memset(mark, false, sizeof(mark));
  73.  
  74. f(i,n){
  75. f(j,n){
  76. if(i == j) continue;
  77. if(r[i].above(r[j])) r[i].add(j);
  78. }
  79. }
  80.  
  81. f(i,n){
  82. if(r[i] == r[n]){
  83. printf("%d\n", dfs(i)-1);
  84. }
  85. }
  86. }
  87.  
  88. int main(){
  89. while(read())process();
  90. return 0;
  91. }
Add Comment
Please, Sign In to add comment