Advertisement
Morass

13169

Nov 2nd, 2017
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define PB push_back
  4. #define ZERO (1e-10)
  5. #define INF (1<<29)
  6. #define CL(A,I) (memset(A,I,sizeof(A)))
  7. #define DEB printf("DEB!\n");
  8. #define D(X) cout<<"  "<<#X": "<<X<<endl;
  9. #define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
  10. typedef long long ll;
  11. typedef long double ld;
  12. typedef pair<ll,ll> pll;
  13. typedef vector<int> vi;
  14. typedef pair<int,int> ii;
  15. typedef vector<ii> vii;
  16. #define IN(n) int n;scanf("%d",&n);
  17. #define FOR(i, m, n) for (int i(m); i < n; i++)
  18. #define REP(i, n) FOR(i, 0, n)
  19. #define F(n) REP(i, n)
  20. #define FF(n) REP(j, n)
  21. #define FT(m, n) FOR(k, m, n)
  22. #define aa first
  23. #define bb second
  24. void ga(int N,int *A){F(N)scanf("%d",A+i);}
  25. #define MX (100006)
  26. int C[MX],R[MX],W;
  27. int geco(int a){return C[a]=(a==C[a]?a:geco(C[a]));}
  28. bool con(int a,int b){
  29.     if(geco(a)==geco(b))return 0;
  30.     if(R[C[a]]>R[C[b]])C[C[b]]=C[a];
  31.     else R[C[b]]+=R[C[a]]==R[C[b]],C[C[a]]=C[b];
  32.     return --W,1;
  33. }
  34. #define CLR (iota(C,C+D,0),CL(R,0),W=D)
  35. int N,X[MX],Y[MX],Z[MX],x[MX],y[MX],z[MX],D,a,b;
  36. unordered_map<int,int> T;
  37. set<ii> S;
  38. int gw(int x,int y,int z){
  39.     int H=x+y*1000+z*1000000;
  40.     if(!T.count(H))T[H]=D++;
  41.     return T[H];
  42. }
  43. bool ccl(bool p){
  44.     T.clear(),D=0,S.clear();
  45.     F(N){
  46.         a=gw(X[i],Y[i],p*Z[i]),b=gw(x[i],y[i],p*z[i]);
  47.         if(a^b)S.insert({min(a,b),max(a,b)});
  48.     }
  49.     CLR;
  50.     for(auto&h:S)if(!con(h.aa,h.bb))return 0;
  51.     return 1;
  52. }
  53. int main(void){
  54.     while(~scanf("%d",&N)){
  55.         F(N)scanf("%d%d%d%d%d%d",X+i,Y+i,Z+i,x+i,y+i,z+i);
  56.         puts(!ccl(1)?"True closed chains":"No true closed chains");
  57.         puts(!ccl(0)?"Floor closed chains":"No floor closed chains");
  58.     }
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement