Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2016-05-28 12:21:59
Task:Graph painting
Sender:Barely Div 1
Submission time:2016-05-28 12:21:59
Status:READY
Result:ACCEPTED

Show test data

Code

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <utility>

using namespace std;

typedef int64_t LL;

void solve(){
  int nVertices, nEdges;
  cin >> nVertices >> nEdges;
  vector<pair<int,int> > edges;
  for(int i = 0; i < nEdges; i++){
    int u,v; cin >> u >> v; u--; v--;
    edges.push_back({u,v});
  }
  vector<int> colors(nVertices);
  while(true){
    for(int i = 0; i < nVertices; i++){
      colors[i] = rand() % 2;
    }
    int good = 0;
    for(auto edge : edges){
      if(colors[edge.first] != colors[edge.second]) good++;
    }
    if(good >= nEdges/2){
      for(int i = 0; i < nVertices; i++){
	if(colors[i] == 1) cout << "R ";
	else cout << "B ";
      }
      cout << "\n";
      return;
    }
  }
  
  
}

int main(){
  srand(345348345);
  LL t; cin >> t;
  while(t--) solve();
}