Submission #1067483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067483		juicy	Park (JOI17_park)	C++17	100 / 100	227 ms	960 KiB

park

#include "park.h"

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1400;

int n;
int Place[MAX], flg[MAX];
bool vis[MAX];
vector<int> g[MAX];

void add(int u, int v) {
  g[u].push_back(v);
  g[v].push_back(u);
  Answer(min(u, v), max(u, v));
} 

int qry(int u, int v) {
  return Ask(min(u, v), max(u, v), Place);
}

vector<int> ord;

void dfs(int u) {
  vis[u] = 1;
  ord.push_back(u);
  for (auto v : g[u]) {
    if (!vis[v] && flg[v] != 3) {
      dfs(v);
    }
  }
}

void solve(int u) {
  flg[u] = 2;
  while (1) {
    for (int i = 0; i < n; ++i) {
      Place[i] = flg[i] == 1;
    }
    Place[u] = 1;
    if (qry(0, u)) {
      break;
    } 
    vector<int> cands;
    for (int i = 0; i < n; ++i) {
      if (!flg[i]) {
        cands.push_back(i);
      }
    }
    int l = 0, r = cands.size() - 1, p = -1;
    while (l <= r) {
      int md = (l + r) / 2;
      for (int i = 0; i < cands.size(); ++i) {
        Place[cands[i]] = i <= md;
      }
      if (qry(0, u)) {
        p = cands[md];
        r = md - 1;
      } else {
        l = md + 1;
      }
    }
    solve(p);
  }
  vector<int> cands{0};
  for (int i = 0; i < cands.size(); ++i) {
    int x = cands[i];
    if (flg[x] == 3) {
      continue;
    }
    memset(vis, 0, sizeof(vis));
    vector<int>().swap(ord);
    dfs(x);
    for (int it = 0; it < n; ++it) {
      Place[it] = 0;
    }
    for (int v : ord) {
      Place[v] = 1;
    }
    Place[u] = 1;
    if (!qry(x, u)) {
      continue;
    }
    int l = 0, r = ord.size() - 1, p = -1;
    while (l <= r) {
      int md = (l + r) / 2;
      for (int j = 0; j < ord.size(); ++j) {
        Place[ord[j]] = j <= md;
      }
      if (qry(x, u)) {
        p = ord[md];
        r = md - 1;
      } else {
        l = md + 1;
      }
    }
    flg[p] = 3;
    for (auto v : g[p]) {
      cands.push_back(v);
    }
    add(u, p);
  }
  flg[u] = 1;
  for (int i = 0; i < n; ++i) {
    if (flg[i] == 3) {
      flg[i] = 1;
    }
  }
}

void Detect(int T, int N) {
  n = N;
  flg[0] = 1;
  for (int i = 1; i < N; ++i) {
    if (!flg[i]) {
      solve(i);
    }
  }
}

Compilation message (stderr)

park.cpp: In function 'void solve(int)':
park.cpp:55:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |       for (int i = 0; i < cands.size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~
park.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for (int i = 0; i < cands.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~
park.cpp:89:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |       for (int j = 0; j < ord.size(); ++j) {
      |                       ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23