Submission #295502

#	Time	Username	Problem	Language	Result	Execution time	Memory
295502		tzero	Split the Attractions (IOI19_split)	C++14	0 / 100	1 ms	384 KiB

split

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <cassert>
using namespace std;
vector<vector<int> > adj;
vector<pair<int,int> > colors;
vector<int> sub, ans;
int c_idx;

int dfs(int a, int p) {
  sub[a] = 0;
  for(int b : adj[a]) if(b != p) {
    sub[a] += dfs(b, a);
  }
  return sub[a];
}

void dfs2(int a, vector<int> & ans, int color) {
  ans[a] = color;
  for(int b : adj[a]) if(sub[b] < sub[a]) {
    dfs2(b, ans, color);
  }
}

void dfs3(int a, int p) {
  ans[a] = colors[c_idx].second;
  colors[c_idx].first--;
  if(colors[c_idx].first == 0) c_idx++;

  for(int b : adj[a]) if(b != p && ans[b] == 0) {
    dfs3(b, a);  
  }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  adj.resize(n);
  ans.assign(n, 0);

  for(int i = 0; i < (int)p.size(); i++) {
    adj[p[i]].push_back(q[i]);
    adj[q[i]].push_back(p[i]);
  }

  bool two_endpoints = true;
  for(int i = 0; i < n; i++) {
    if(adj[i].size() > 2) two_endpoints = 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_endpoints) {
    int found = -1;
    c_idx = 0;
    for(int i = 0; found == -1 && i < n; i++) {
      if(adj[i].size() == 1) {
        found = i;
      }
      dfs3(found, found);
    }

    if(found == -1) {
      dfs3(0, 0);
    }

    return ans;

  } else if(p.size() == n - 1) { // tree
    sub.resize(n);
    dfs(0, 0);  

    int possible = -1;
    int smallest = colors[0].first;
    int medium = colors[1].first;

    for(int i = 0; i < n && possible == -1; i++) {
      if(sub[i] >= smallest && n - sub[i] >= medium) {
        possible = i;
      } else if(sub[i] >= medium && n - sub[i] >= smallest) {
        assert(false); // Why the fuck would this happen?
        possible = i;
      }
    }

    if(possible != -1) {
      dfs2(possible, ans, colors[0].second);  
      dfs2(possible, ans, colors[1].second);
      for(int i = 0; i < n; i++) if(ans[i] == 0) {
        ans[i] = colors[2].second;  
      }
    }

    return ans;

  } else if(true || a == 1) {
    return ans;
  }
}

int my_main() {
  int n, m, a, b, c;
  cin >> n >> m >> a >> b >> c;

  vector<int> p(m), pp(m);
  for(int i = 0; i < m; i++) {
    cin >> p[i] >> pp[i];
  }

  vector<int> _ans = find_split(n, a, b, c, p, pp);
  for(int x : _ans) {
    cout << x << " ";
  }
  cout << endl;

  return 0;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:72:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |   } else if(p.size() == n - 1) { // tree
      |             ~~~~~~~~~^~~~~~~~

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