Submission #443308

#	Time	Username	Problem	Language	Result	Execution time	Memory
443308		mkisic	Split the Attractions (IOI19_split)	C++14	22 / 100	786 ms	1048580 KiB

split

#include "split.h"
#include <queue>
#include <cassert>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair <int, int> pii;

#define TRACE(x) cerr << #x << ' ' << x << endl
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define _ <<  " " << 

#define fi first
#define sec second

#define pb push_back

const int MAXN = 200100;

int n;

vector <int> v[MAXN];
vector <int> bio;

bool bfs(int start, vector <int> boje, vector <int> &ret) {
  queue <int> q;
  bio[start] = 1;
  int cnt = 0;
  q.push(start);
  vector <int> pos;
  while (!q.empty()) {
    int cvor = q.front();
    q.pop();
    cnt++;
    pos.pb(cvor);
    if (cnt == min(boje[2], boje[3])) {
      int boja = 3;
      if (boje[3] > boje[2]) boja = 2;
      for (auto &x : pos) ret[x] = boja;
      return true;
    }

    for (auto &ncvor : v[cvor]) {
      if (bio[ncvor]) continue;
      bio[ncvor] = 1;
      q.push(ncvor);
    }

  }
  return false;
}

vector <int> solve1(vector <int> boje) {
  vector <int> ret;
  ret.resize(n);

  REP(i, n) {
    if (bio[i]) continue;
    if (bfs(i, boje, ret)) {
      int boja = 2;
      if (boje[3] > boje[2]) boja = 3;
      REP(j, n) {
        if (ret[j] == 0 && boje[1]) {
          ret[j] = 1;
          boje[1]--;
        } else if (ret[j] == 0) ret[j] = boja;
      }
      return ret;
    }
  }

  return ret;
}

int sub[MAXN];

void dfs(int cvor, int par) {
  sub[cvor]++;
  for (auto &ncvor : v[cvor]) {
    if (ncvor == par) continue;
    dfs(ncvor, cvor);
    sub[cvor] += sub[ncvor];
  }
}

void bojaj(int cvor, int par, int boja, vector <int> &boje, vector <int> &ret) {
  if (boje[boja] == 0) return;
  ret[cvor] = boja;
  boje[boja]--;
  for (auto &ncvor : v[cvor]) {
    if (par == ncvor) continue;
    bojaj(ncvor, cvor, boja, boje, ret);
  }
}

vector <int> rezi(int A, int B, vector <int> boje, int ka, int kb) {
  vector <int> ret;
  ret.resize(n);
  bojaj(A, B, ka, boje, ret);
  bojaj(B, A, kb, boje, ret);
  REP(i, n) if (!ret[i]) ret[i] = 6 - ka - kb;
  return ret;
}

vector <int> stablo(vector <int> boje) {
  dfs(0, -1);
  vector <pii> B;
  FOR(i, 1, 4) B.pb({boje[i], i});
  sort(B.begin(), B.end());
  REP(i, MAXN) {
    for (auto &j : v[i]) {
      int x = i, y = j;
      if (sub[x] > sub[y]) swap(x, y);
      int ostalo = n - sub[x];
      if (ostalo >= B[0].fi && sub[x] >= B[1].fi) {
        return rezi(y, x, boje, B[0].sec, B[1].sec);
      }
      if (ostalo >= B[1].fi && sub[x] >= B[0].fi) {
        return rezi(x, y, boje, B[0].sec, B[1].sec);
      }
    }
  }
  vector <int> ret;
  ret.resize(n);
  return ret;
}

vector <int> tmp;

void f(int cvor, int par) {
  tmp.pb(cvor);
  bio[cvor] = 1;
  for (auto &ncvor : v[cvor]) {
    if (par == ncvor) continue;
    f(ncvor, cvor);
  }
}

bool cmp(const vector <int> &a, const vector <int> &b) {
  return a.size() < b.size();
}

vector <int> lanci(vector <int> boje) {
  vector <pii> B;
  FOR(i, 1, 4) B.pb({boje[i], i});
  sort(B.begin(), B.end());
  vector <vector <int> > l;
  REP(i, n) {
    if (!bio[i]) {
      tmp.clear();
      f(i, -1);
      l.pb(tmp);
    }
  }
  sort(l.begin(), l.end(), cmp);
  int tu = 0;
  vector <int> ret;
  ret.resize(n);
  for (auto &L : l) {
    if (L.size() >= B[tu].fi) {
      REP(i, B[tu].fi) ret[L[i]] = B[tu].sec;
      int ostalo = L.size() - B[tu].fi;
      tu++;
      if (tu == 2) break;
      if (ostalo >= B[tu].fi) {
        FOR(i, B[tu -1].fi, B[tu-1].fi + B[tu].fi) {
          ret[L[i]] = B[tu].sec;
        }
      }
      tu++;
      break;
    }
  }
  if (tu == 2) {
    REP(i, n) if (!ret[i]) ret[i] = B[2].sec;
  } else {
    ret.clear();
    ret.resize(n);
  }
  return ret;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
  n = N;
  bio.resize(n);
  REP(i, p.size()) {
    v[p[i]].pb(q[i]);
    v[q[i]].pb(p[i]);
  }
  vector <int> boje = {0, a, b, c};

  int deg = 0;
  REP(i, n) deg = max(deg, (int)v[i].size());

  if (deg <= 2) return lanci(boje);
  if (p.size() == n - 1) return stablo(boje);
  return solve1(boje);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> lanci(std::vector<int>)':
split.cpp:164:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  164 |     if (L.size() >= B[tu].fi) {
      |                  ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:13:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
split.cpp:14:19: note: in expansion of macro 'FOR'
   14 | #define REP(i, n) FOR(i, 0, n)
      |                   ^~~
split.cpp:190:3: note: in expansion of macro 'REP'
  190 |   REP(i, p.size()) {
      |   ^~~
split.cpp:200:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  200 |   if (p.size() == n - 1) return stablo(boje);
      |       ~~~~~~~~~^~~~~~~~

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