oj.uz

Submission #94782

# Submission time Handle Problem Language Result Execution time Memory
94782 2019-01-23T20:37:47 Z tincamatei ICC (CEOI16_icc) C++14
61 / 100
 193 ms 632 KB 
#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;

mt19937 mt_rand(time(NULL));

bool randomSplit(int n, vector<int> &sa, vector<int> &sb) {
  for(int i = 1; i <= n; ++i)
    rperm[i] = mt_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) {
  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

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:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sa.size(); ++i)
                  ~~^~~~~~~~~~~
icc.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < sb.size(); ++i)
                  ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Ok! 113 queries used.
2 Correct 7 ms 508 KB Ok! 111 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 504 KB Ok! 558 queries used.
2 Correct 56 ms 504 KB Ok! 871 queries used.
3 Correct 54 ms 504 KB Ok! 815 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 604 KB Ok! 1551 queries used.
2 Correct 193 ms 632 KB Ok! 2228 queries used.
3 Correct 143 ms 504 KB Ok! 1653 queries used.
4 Correct 151 ms 504 KB Ok! 1757 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 560 KB Ok! 1712 queries used.
2 Correct 149 ms 632 KB Ok! 1716 queries used.
3 Correct 162 ms 504 KB Ok! 1917 queries used.
4 Correct 136 ms 568 KB Ok! 1596 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 556 KB Too many queries! 1872 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 564 KB Too many queries! 1931 out of 1625
2 Halted 0 ms 0 KB -