Submission #265032

#	Time	Username	Problem	Language	Result	Execution time	Memory
265032		Bruteforceman	Split the Attractions (IOI19_split)	C++14	0 / 100	677 ms	1048580 KiB

split

#include "bits/stdc++.h"
#include "split.h"
using namespace std;
const int maxn = 1e5 + 10;
vector <int> g[maxn];
int sub[maxn];

void dfs(int x, int par) {
  sub[x] = 1;
  for(int i : g[x]) {
    if(i != par) {
      dfs(i, x);
      sub[x] += sub[i];
    }
  }
}
int centroid(int x, int par, int range) {
  for(int i : g[x]) {
    if(i != par && range < sub[i]) {
      return centroid(i, x, range);
    }
  }
  return x;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  vector <int> res (n, 0);
  int valA, valB, valC;
  if(a > b) {
    swap(a, b);
    swap(valA, valB);
  }
  if(b > c) {
    swap(b, c);
    swap(valB, valC);
  }
  if(a > b) {
    swap(a, b);
    swap(valA, valB);
  }
  for(int i = 0; i < p.size(); i++) {
    g[p[i]].push_back(q[i]);
    g[q[i]].push_back(p[i]);
  }
  dfs(0, -1);
  int root = centroid(0, -1, n / 2);
  dfs(root, -1);
  function <void(int, int, vector <int> &)> getNodes = [&] (int x, int par, vector <int> &v) {
    v.push_back(x);
    for(int i : g[x]) {
      if(i != par && res[i] == 0) {
        getNodes(i, x, v);
      }
    }
    return ;
  };
  for(int i : g[root]) {
    if(sub[i] >= a) {
      vector <int> v;
      getNodes(i, c, v);
      for(int j : v) res[j] = valA;
    }
  }
  if(*max_element(res.begin(), res.end()) == 0) return res;
  vector <int> v;
  getNodes(c, -1, v);
  int tmp = b;
  for(int i : v) {
    if(tmp > 0) {
      tmp -= 1;
      res[i] = valB;
    } else {
      res[i] = valC;
    }
  }
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
split.cpp:61:29: warning: 'valC' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |       for(int j : v) res[j] = valA;
split.cpp:71:14: warning: 'valB' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |       res[i] = valB;
split.cpp:73:14: warning: 'valA' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |       res[i] = valC;

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