Advertisement
Guest User

Untitled

a guest
Dec 20th, 2014
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8.  
  9. vector<int> v[202020];
  10. int q[202020];
  11.  
  12. int h[202020];
  13.  
  14. int main() {
  15. srand(1337);
  16. cin >> n;
  17. for (int i = 0; i < 5; i++) {
  18. int c;
  19. cin >> c;
  20. for (int j = 0; j < c; j++) {
  21. int a, b;
  22. cin >> a >> b;
  23. bool ok = true;
  24. for (int k = 0; k < v[a].size(); k++) {
  25. if (v[a][k] == b) ok = false;
  26. }
  27. if (!ok) continue;
  28. v[a].push_back(b);
  29. v[b].push_back(a);
  30. }
  31. }
  32. for (int i = 1; i <= n; i++) q[i] = rand()%2;
  33.  
  34. for (int i = 1; i <= n; i++) h[i] = i;
  35. for (int i = 1; i <= n; i++) {
  36. swap(h[i], h[i+rand()%(n-i+1)]);
  37. }
  38.  
  39. while (true) {
  40. bool ok = true;
  41. for (int x = 1; x <= n; x++) {
  42. int i = h[x];
  43. int a = q[i];
  44. int z = 0;
  45. for (int j = 0; j < v[i].size(); j++) {
  46. if (q[v[i][j]] == a) z++;
  47. }
  48. if (z <= 2) continue;
  49. ok = false;
  50. q[i] = 1-q[i];
  51. }
  52. if (ok) break;
  53. }
  54. for (int i = 1; i <= n; i++) {
  55. if (q[i] == 0) cout << "A";
  56. else cout << "B";
  57. }
  58. cout << "\n";
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement