fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define LL long long
  3. #define ULL unsigned long long
  4. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  5. #define FO(i,a,b) for(int i=a;i<b;i++)
  6. #define FORD(i,a,b) for(int i=a;i>=b;i--)
  7. #define FOD(i,a,b) for(int i=a;i>b;i--)
  8. #define FORV(i,a) for(typeof(a.begin()) i = a.begin(); i != a.end(); i++)
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define mp make_pair
  13.  
  14. using namespace std;
  15.  
  16. #define maxn 200005
  17.  
  18. int n, m, u, v;
  19. vector<int> adj[maxn];
  20. int cnt[maxn];
  21. bool color[maxn];
  22.  
  23. int find2(){
  24.     int ok = rand()%2;
  25.     if(ok == 1){
  26.         FOR(u,1,n){
  27.             if(cnt[u] > 2) return u;
  28.         }
  29.     }
  30.     else{
  31.         FORD(u,n,1){
  32.             if(cnt[u] > 2) return u;
  33.         }
  34.     }
  35.     return 0;
  36. }
  37.  
  38. void update(int u){
  39.     int tmp = 0;
  40.     FO(i,0,adj[u].size()){
  41.         int v = adj[u][i];
  42.         if(color[u] == color[v]) cnt[v]--;
  43.         else{
  44.             cnt[v]++;
  45.             tmp++;
  46.         }
  47.     }
  48.     cnt[u] = tmp;
  49.     color[u] = !color[u];
  50. }
  51.  
  52. void solve(){
  53.     FOR(u,1,n)
  54.         if(rand()%2) color[u] = 1;
  55.         else color[u] = 0;
  56.     FOR(u,1,n){
  57.         FO(i,0,adj[u].size()){
  58.             int v = adj[u][i];
  59.             if(color[u] == color[v]) cnt[u]++;
  60.         }
  61.     }
  62.  
  63.     while(1){
  64.         int pos = find2();
  65.         if(pos == 0) break;
  66.         update(pos);
  67.     }
  68.     FOR(i,1,n){
  69.         if(color[i] == 1) cout << "A";
  70.         else cout << "B";
  71.     }
  72.     cout << endl;
  73. }
  74.  
  75.  
  76. int main() {
  77.     srand(time(0));
  78.     ios::sync_with_stdio(false);
  79.     #ifndef ONLINE_JUDGE
  80.     //freopen("test.in", "r", stdin);
  81.     //freopen("test.out", "w", stdout);
  82.     #endif
  83.     cin >> n;
  84.     FOR(k,1,5){
  85.         cin >> m;
  86.         while(m--){
  87.             cin >> u >> v;
  88.             adj[u].pb(v);
  89.             adj[v].pb(u);
  90.         }
  91.     }
  92.     solve();
  93.  
  94.  
  95.     return 0;
  96. }
  97.  
Success #stdin #stdout 0s 6800KB
comments (?)
stdin
copy 
10
3 1 2 7 3 9 4
3 1 3 7 4 9 5
3 1 4 7 5 9 6
3 1 5 7 6 9 8
3 1 6 7 8 9 10
stdout
copy 
BBAAAABBBA
https://ideone.com/FQtOdy
language:
C++ (gcc 8.3)
created:
9 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!