CSES - HIIT Open 2016 - Results
Submission details
Task:Graph painting
Sender:Oispa Kaljaa
Submission time:2016-05-28 12:25:39 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.07 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.13 sdetails

Code

#include <bits/stdc++.h>

using namespace std;

int main(){
  cin.sync_with_stdio(0);
  cin.tie(0);
  
  int tests; cin >> tests;
  
  while(tests--){
      vector<int> v[101010];
      int n, m; cin >> n >> m;
      bool ans[101010] = {0};
      for(int i = 0; i < m; i++){
	int a, b; cin >> a >> b;
	v[a].push_back(b);
	v[b].push_back(a);
      }
      vector<pair<int, int>> vs;
      for(int i = 1; i <= n; i++)
	vs.push_back({v[i].size(), i});
      sort(vs.begin(), vs.end());
      int cc = 0;
      for(int i = n-1; i >= 0; i--){
	int cur = vs[i].second;
	
	int ad = 0;
	for(auto f: v[cur]){
	  if(ans[f] == 0){
	    ad++;
	  }
	  else
	    ad--;
	}
	if(ad > 0){
	  cc+=ad;
	  ans[cur] = 1;
	}
	
	if(cc >= m/2)
	  break;
      }
      for(int i = 1; i <= n; i++){
	if(ans[i] == 1)
	  cout << 'R' << " ";
	else
	  cout << 'B' << " ";
      }
      cout << endl;
	
  } 
  return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
100
7 1
2 5
8 28
2 7
...

correct output
B R B B B B R 
R B B R B R B B 
R R B B B B R R R B 
B B R B R B 
B B B R B R R B R 
...

user output
B B B B R B B 
B B B B B R R R 
B B B B B B R B R B 
B B B B R R 
B B B B B R R B B 
...

Test 2

Verdict: ACCEPTED

input
10
38 36
18 28
20 37
22 38
...

correct output
R R B R B R R R R R B B R B R ...

user output
B B B B B B B B B B B B B B B ...

Test 3

Verdict: ACCEPTED

input
1
100000 200000
89300 98492
33853 56822
92967 99427
...

correct output
R R R R B R R R B B B R B B B ...

user output
B B B B B B B B B B B B B B B ...