제출 #95499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95499		tincamatei	Towns (IOI15_towns)	C++14	0 / 100	18 ms	1144 KiB

towns

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

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39