Submission #679820

#	Time	Username	Problem	Language	Result	Execution time	Memory
679820		cadmiumsky	Split the Attractions (IOI19_split)	C++14	100 / 100	164 ms	26648 KiB

split

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

#define sz(x) (int)(x).size()

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 1e5 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
vector<int> leg[nmax];

struct Tree {
  vector<int> g[nmax];
  int root;
  void clear() {
    for(int i = 0; i < n; i++)
      g[i].clear();
    return;
  }
  void addedge(int a, int b) {
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  vector<int> togive;
  int mxarea[nmax], area[nmax], p[nmax];
  
  void down(int node, int f) {
    p[node] = f;
    for(auto x : g[node]) {
      if(x == f) continue;
      down(x, node);
      area[node] += area[x];
      mxarea[node] = max(mxarea[node], area[x]);
    }
    area[node]++;
  }
  void init() { togive.resize(n, 0); down(root, root); }
  
  
  void fillgreedy(int node, int f, int& a) {
    if(a == 0) return;
    sort(all(g[node]), [&](int x, int b) { return area[x] < area[b] || (area[x] > a && area[b] > a && mxarea[x] < mxarea[b]); });
    togive[node] = 1;
    a--;
    for(auto x : g[node]) {
      if(x == f) continue;
      fillgreedy(x, node, a);
      if(a == 0) return;
    }
  }
  
  vector<int> getbydown(int a) {
    std::fill(all(togive), 0);
    int best = root;
    for(int i = 0; i < n; i++)
      if(area[i] >= a && area[best] > area[i]) best = i;
    fillgreedy(best, p[best], a);
    return togive;
  }
  
  vector<int> getbyroot(int a) {
    std::fill(all(togive), 0);
    fillgreedy(root, root, a);
    return togive;
  }
  
  int flag = 2;
  int fill(int node, vector<int>& occ, int& b) {
    if(b == 0) return 0;
    if(occ[node] != 0) return 0;
    occ[node] = flag;
    int sum = 1;
    b--;
    for(auto x : leg[node])
      sum += fill(x, occ, b);
    return sum;
  }
  
  void fill(vector<int> &occ, int b) {
    for(int i = 0; i < n; i++) {
      if(occ[i] == 0) {
	flag++;
	int tmp = b;
	fill(i, occ, b);
	if(b == 0) {
	  //for(auto x : occ)
	    //cerr << x << ' ';
	  //cerr << '\n';
	  //cerr << flag << '\n';
	  for(auto &x : occ) {
	    if(x == 1) continue;
	    if(x == flag) x = 2;
	    else x = 3;
	  }
	  return;
	}
	b = tmp;
      }
    }
    occ.back() = -1;
    return;
  }
} tree;

int occ[nmax];

void dfs(int node) {
  if(occ[node] == 1) return;
  occ[node] = 1;
  for(auto x : leg[node]) {
    if(occ[x] == 0) {
      tree.addedge(node, x);
      dfs(x);
    }
  }
  return;
}

void constr_tree(vector<pii>& edg, int rt) {
  tree.clear();
  for(int i = 0; i < n; i++)
    leg[i].clear();
  for(auto [a, b] : edg)
    leg[a].emplace_back(b),
    leg[b].emplace_back(a);
  
  tree.root = rt;
  dfs(rt);
  tree.init();
}

int rnd(int x) {return rng() % x;}
vector<int> sol;
void verif(int node, int col) {
  sol[node] = -1;
  for(auto x : leg[node]) {
    if(sol[x] == col) {
      verif(x, col);
    }
  }
}

std::vector<int> find_split(int N, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
  n = N;
  int hsh[3] = {0, 1, 2};
  { // renumerotare
    if(a > b)
      swap(hsh[0], hsh[1]),
      swap(a, b);
    if(b > c)
      swap(hsh[1], hsh[2]),
      swap(b, c);
    if(a > b)
      swap(hsh[0], hsh[1]),
      swap(a, b);
  }
  
  vector<pii> edg;
  for(int i = 0; i < sz(p); i++)
    edg.emplace_back(p[i], q[i]);
  
  vector<int> var(n, -1);
  
  int counted = 0;
  int sus = 0;
  do {
    constr_tree(edg, sus);
    vector<int> var1 = tree.getbydown(a), var2 = tree.getbyroot(a);
    tree.fill(var1, b);
    tree.fill(var2, b);
    
    if(var1.back() == -1)	
      swap(var1, var2);
    var = move(var1);
    counted++;
    random_shuffle(all(edg), rnd);
    //sus = rnd(n);
  } while(var.back() == -1 && counted < 1);
  if(var.back() == -1) {
    fill(all(var), 0);
    return var;
  }
  sol = var;
  int cnts = 0;
  for(int i = 0; i < n; i++) {
    if(sol[i] == 1)
      cnts++,
      verif(i, 1);
    if(sol[i] == 2)
      cnts++,
      verif(i, 2);
  }
  //cerr << cnts << '\n';
  assert(cnts == 2);
  int cnt[3] = {0, 0, 0};
  for(auto &x : var) {
    x--;
    x = hsh[x];
    x++;
  }
  return var;
}

Compilation message (stderr)

split.cpp: In function 'void constr_tree(std::vector<std::pair<int, int> >&, int)':
split.cpp:130:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |   for(auto [a, b] : edg)
      |            ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:202:7: warning: unused variable 'cnt' [-Wunused-variable]
  202 |   int cnt[3] = {0, 0, 0};
      |       ^~~

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