제출 #95750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95750		tincamatei	도시들 (IOI15_towns)	C++14	13 / 100	38 ms	1016 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 dist[110][110];

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

  for(int i = 0; i < N; ++i)
    for(int j = i + 1; j < N; ++j) {
      dist[i][j] = dist[j][i] = getDistance(i, j);
      if(dist[i][j] > diam) {
        diam = dist[i][j];
        c1 = i;
        c2 = j;
      }
    }

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

  for(int i = 0; i < N; ++i) {
    int dx, dy;
    int dc1c, dc2c, dic;
    dx = dist[c1][i];
    dy = dist[c2][i];
    //x = getDistance(c1, i);
    //y = getDistance(c2, i);

    dic = (dx + dy - diam) / 2;
    dc1c = dx - dic;
    dc2c = dy - 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.swap(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:24:28: warning: unused parameter 'subtask' [-Wunused-parameter]
 int hubDistance(int N, int subtask) {
                            ^~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39