Submission #295531

#	Time	Username	Problem	Language	Result	Execution time	Memory
295531		tzero	Split the Attractions (IOI19_split)	C++14	7 / 100	98 ms	11644 KiB

split

#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
const int maxn = (int)1e5+7;
int color_idx;
vector<int> adj[maxn];
vector<int> ans;
vector<pair<int,int> > colors;

void dfs1(int a) {
  ans[a] = colors[color_idx].second;
  colors[color_idx].first--;
  if(colors[color_idx].first == 0) color_idx++;

  for(int b : adj[a]) if(ans[b] == 0) {
    dfs1(b);
  }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  for(int i = 0; i < (int)q.size(); i++) {
    adj[q[i]].push_back(p[i]);  
    adj[p[i]].push_back(q[i]);
  }

  ans.assign(n, 0);

  bool two_max = true;
  for(int i = 0; i < n; i++) {
    if((int)adj[i].size() > 2) {
      two_max = false; 
    }
  }

  colors.push_back(make_pair(a, 1));
  colors.push_back(make_pair(b, 2));
  colors.push_back(make_pair(c, 3));
  sort(colors.begin(), colors.end());

  if(two_max) {
    // find a leaf
    bool found = false;
    color_idx = 0;

    for(int i = 0; found && i < n; i++) {
      if((int)adj[i].size() == 1) {
        found = true;
        dfs1(i);
      }
    }

    if(!found) {
      dfs1(0);
    }

    assert(colors[0].first + colors[1].first + colors[2].first == 0); 
    return ans;

  } else {
    return ans;
  }
}

int my_main() { 
  int n, m;
  cin >> n >> m;
  int a, b, c;
  cin >> a >> b >> c;
  vector<int> p(m), q(m);
  for(int i = 0; i < m; i++) {
    cin >> p[i] >> q[i];
  }
  vector<int> res = find_split(n, a, b, c, p, q);
  for(int x : res) cout << x << " ";
  cout << endl;
}

Compilation message (stderr)

split.cpp: In function 'int my_main()':
split.cpp:78:1: warning: no return statement in function returning non-void [-Wreturn-type]
   78 | }
      | ^

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36