Submission #443296

#	Time	Username	Problem	Language	Result	Execution time	Memory
443296		mkisic	Split the Attractions (IOI19_split)	C++14	11 / 100	97 ms	13152 KiB

split

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

#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 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;
}

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};
  return solve1(boje);


}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:11:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
split.cpp:12:19: note: in expansion of macro 'FOR'
   12 | #define REP(i, n) FOR(i, 0, n)
      |                   ^~~
split.cpp:77:3: note: in expansion of macro 'REP'
   77 |   REP(i, p.size()) {
      |   ^~~

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