Submission #94780

#	Time	Username	Problem	Language	Result	Execution time	Memory
94780		tincamatei	ICC (CEOI16_icc)	C++14	61 / 100	190 ms	632 KiB

icc

#include <bits/stdc++.h>

using namespace std;

#ifdef HOME

int edges = 1;
int timestamp[101][101];

int nrqueries;

int query(int size_a, int size_b, int a[], int b[]) {
  ++nrqueries;
  for(int i = 0; i < size_a; ++i)
    for(int j = 0; j < size_b; ++j)
      if(timestamp[a[i]][b[j]] <= edges || timestamp[b[j]][a[i]] <= edges) {
        return 1;
      }
  return 0;
}

void setRoad(int a, int b) {
  printf("Set road: %d %d\n", a, b);
  if(timestamp[a][b] == edges || timestamp[b][a] == edges)
    ++edges;
  else {
    printf("Wrong Edge\n");
    exit(0);
  }
}

#else

#include "icc.h"

int query(int, int, int *, int *);
void setRoad(int a, int b);

#endif

const int MAX_N = 100;

int a[MAX_N], b[MAX_N], topa, topb;
int sef[1+MAX_N];
int rperm[1+MAX_N];

int myfind(int x) {
  if(x == sef[x]) return x;

  sef[x] = myfind(sef[x]);
  return sef[x];
}

void myunion(int a, int b) {
  int sa = myfind(a), sb = myfind(b);
  sef[sa] = sb;
}

int bsqueries;

int binsrc(const vector<int> &sa, const vector<int> &sb) {
  int st = -1, dr = (int)sa.size() - 1;

  topa = 0;
  for(int i = 0; i < sb.size(); ++i)
    a[topa++] = sb[i];

  while(dr - st > 1) {
    int mid = (st + dr) / 2;

    topb = 0;
    for(int i = 0; i <= mid; ++i)
      b[topb++] = sa[i];

    ++bsqueries;
    assert(bsqueries < 1400);
    if(query(topa, topb, a, b))
      dr = mid;
    else
      st = mid;
  }

  return sa[dr];
}

void solveSplit(const vector<int> sa, const vector<int> sb) {
  int n1, n2;
  n1 = binsrc(sa,   sb);
  n2 = binsrc(sb, {n1});

  setRoad(n1, n2);
  myunion(n1, n2);
}

int expected;

bool randomSplit(int n, vector<int> &sa, vector<int> &sb) {
  for(int i = 1; i <= n; ++i)
    rperm[i] = rand() % 2;
  sa.clear();
  sb.clear();
  for(int i = 1; i <= n; ++i) {
    if(rperm[myfind(i)] % 2 == 0)
      sa.push_back(i);
    else
      sb.push_back(i);
  }

  topa = topb = 0;
  for(int i = 0; i < sa.size(); ++i)
    a[topa++] = sa[i];
  for(int i = 0; i < sb.size(); ++i)
    b[topb++] = sb[i];

  expected++;
  //assert(expected < 400); // Expected Value screwed me over

  if(query(topa, topb, a, b))
    return true;
  return false;
}

void split(int n, vector<int> &sa, vector<int> &sb) {
  while(!randomSplit(n, sa, sb));
}

void run(int n) {
  srand(time(NULL));

  for(int i = 1; i <= n; ++i)
    sef[i] = i;

  for(int i = 0; i < n - 1; ++i) {
    vector<int> sa, sb;
    split(n, sa, sb);
    solveSplit(sa, sb);
  }
}

#ifdef HOME

int main() {
  int n;

  FILE *fin = fopen("icc.in", "r");

  fscanf(fin, "%d", &n);

  for(int i = 0; i <= n; ++i)
    for(int j = 0; j <= n; ++j)
      timestamp[i][j] = 10000;

  for(int i = 1; i <= n - 1; ++i) {
    int a, b;
    fscanf(fin, "%d%d", &a, &b);
    timestamp[a][b] = i;
  }

  run(n);
  printf("OK! %d queries used\n", nrqueries);

  fclose(fin);
  return 0;
}

#endif

Compilation message (stderr)

icc.cpp: In function 'int binsrc(const std::vector<int>&, const std::vector<int>&)':
icc.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sb.size(); ++i)
                  ~~^~~~~~~~~~~
icc.cpp: In function 'bool randomSplit(int, std::vector<int>&, std::vector<int>&)':
icc.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sa.size(); ++i)
                  ~~^~~~~~~~~~~
icc.cpp:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sb.size(); ++i)
                  ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10