oj.uz

Submission #95499

# Submission time Handle Problem Language Result Execution time Memory
95499 2019-02-01T15:40:35 Z tincamatei Towns (IOI15_towns) C++14
0 / 100
 18 ms 1144 KB 
#include "towns.h"
#include <bits/stdc++.h>

using namespace std;

set<pair<int, int> > diameter;
typedef set<pair<int, int> >::iterator seti;
typedef set<pair<int, int> >::reverse_iterator rseti;

vector<pair<int, int> > eraseQueue;

void lazyErase(pair<int, int> x) {
  eraseQueue.push_back(x);
}

void runEraseQueue() {
  for(int i = 0; i < eraseQueue.size(); ++i)
    diameter.erase(eraseQueue[i]);
  eraseQueue.clear();
}

int hubDistance(int N, int subtask) {
  int c1, c2, diam;
  c1 = 0;
  c2 = 1;
  diam = getDistance(0, 1);

  diameter.insert(make_pair(0, 1));
  diameter.insert(make_pair(diam, 1));

  for(int i = 2; i < N; ++i) {
    int x, y;
    int dc1c, dc2c, dic;
    x = getDistance(c1, i);
    y = getDistance(c2, i);

    dic = (x + y - diam) / 2;
    dc1c = x - dic;
    dc2c = y - dic;

    if(dic + dc1c > diam && dic + dc1c > dic + dc2c) {
      //printf("Replace second head %d %d %d\n", dc1c, dc2c, dic);
      rseti a = diameter.rbegin();
      int meeting = dc1c;
      pair<int, int> sub = make_pair(meeting, 0);

      while(a->first >= meeting) {
        sub.second += a->second;
        lazyErase(*a);
        a++;
      }
      runEraseQueue();


      c2 = i;
      diam = dic + dc1c;

      diameter.insert(sub);
      diameter.insert(make_pair(diam, 1));
    } else if(dic + dc2c > diam) {
      //printf("Replace first head\n");
      seti a = diameter.begin();
      int meeting = dc1c;
      pair<int, int> sub = make_pair(dic, 0);
      set<pair<int, int> > tmp;

      while(a->first <= meeting) {
        sub.second += a->second;
        a++;
      }
      while(a != diameter.end()) {
        tmp.insert(make_pair(a->first + dic - dc1c, a->second));
        a++;
      }
      diameter = tmp;

      c1 = i;
      diam = dic + dc2c;

      diameter.insert(sub);
      diameter.insert(make_pair(0, 1));
    } else {
      //printf("Between\n");
      seti it;
      it = diameter.lower_bound(make_pair(dc1c, -1));
      pair<int, int> x;

      x = *it;
      diameter.erase(it);

      if(x.first == dc1c)
        x.second++;
      else
        diameter.insert(make_pair(dc1c, 1));
      diameter.insert(x);
    }

    //for(seti it = diameter.begin(); it != diameter.end(); it++)
    //  printf("(%d %d)\n", it->first, it->second);
    //printf("\n");
  }

  int rez = 1000000000;
  for(seti it = diameter.begin(); it != diameter.end(); it++)
    rez = min(rez, max(it->first, diam - it->first));

  return rez;
}

Compilation message

towns.cpp: In function 'void runEraseQueue()':
towns.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < eraseQueue.size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:86:22: warning: declaration of 'x' shadows a previous local [-Wshadow]
       pair<int, int> x;
                      ^
towns.cpp:32:9: note: shadowed declaration is here
     int x, y;
         ^
towns.cpp:22:28: warning: unused parameter 'subtask' [-Wunused-parameter]
 int hubDistance(int N, int subtask) {
                            ^~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 1144 KB Output isn't correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -