Submission #265197

#	Time	Username	Problem	Language	Result	Execution time	Memory
265197		Bruteforceman	Split the Attractions (IOI19_split)	C++14	100 / 100	329 ms	30824 KiB

split

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

void makeTree(int x) {
  vis[x] = true;
  for(int i : graph[x]) {
    if(vis[i] == false) {
      g[x].push_back(i);
      g[i].push_back(x);
      makeTree(i);
    }
  }
}
 
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;
}
void assignId(int x, int par, int idx) {
  id[x] = idx;
  cont[idx].push_back(x);
  for(int i : g[x]) {
    if(i != par) {
      assignId(i, x, idx);
    }
  }
}
void getNodes(int x, int &sum, vector <int> &v) {
  if(sum <= 0) return ;
  vis[x] = true;
  v.push_back(x);
  sum -= int(cont[x].size());
  for(int i : aux[x]) {
    if(vis[i] == false) {
      getNodes(i, sum, v);
    }
  }
}
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 = 1, valB = 2, valC = 3;
  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);
  }
  fill(vis, vis + n, false);
  for(int i = 0; i < p.size(); i++) {
    graph[p[i]].push_back(q[i]);
    graph[q[i]].push_back(p[i]);
  }
  makeTree(0);
  dfs(0, -1);
  int root = centroid(0, -1, n / 2);
  for(int i : g[root]) {
    assignId(i, root, i);
  }
  for(int i = 0; i < p.size(); i++) {
    if(p[i] == root || q[i] == root) continue;
    int x = id[p[i]];
    int y = id[q[i]];
    aux[x].push_back(y);
    aux[y].push_back(x);
  }
  bool good = false;
  auto assign = [&] (vector <int> v, int x, int valX) {
    for(int i : v) {
      if(x > 0) {
        res[i] = valX;
        x -= 1;
      }
    }
  };
  function <void(int, int&, int)> assignGraph = [&] (int x, int &cnt, int val) {
    if(cnt <= 0) return ;
    res[x] = val;
    cnt -= 1;
    vis[x] = true;
    for(int i : graph[x]) {
      if(vis[i] == false) {
        assignGraph(i, cnt, val);
      }
    }
  };
  for(int i : g[root]) {
    if(cont[i].size() >= a) {
      good = true;
      assign(cont[i], a, valA);
      break;
    }
  }
  if(not good) {
    fill(vis, vis + n, false);
    for(int i : g[root]) {
      int tmp = a;
      vector <int> v;
      getNodes(i, tmp, v);
      if(tmp <= 0) {
        fill(vis, vis + n, true);
        for(int j : v) for(int k : cont[j]) vis[k] = false; 
        assignGraph(i, a, valA);
        break;
      }
    }
  }
  if(*max_element(res.begin(), res.end()) == 0) return res;
  fill(vis, vis + n, false);
  for(int i = 0; i < n; i++) if(res[i] != 0) vis[i] = true;
  assignGraph(root, b, valB);
  for(int i = 0; i < n; i++) if(res[i] == 0) 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:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
split.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i = 0; i < p.size(); i++) {
      |                  ~~^~~~~~~~~~
split.cpp:115:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |     if(cont[i].size() >= a) {
      |        ~~~~~~~~~~~~~~~^~~~

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