oj.uz

Submission #1067483

# Submission time Handle Problem Language Result Execution time Memory
1067483 2024-08-20T17:51:44 Z juicy Park (JOI17_park) C++17
100 / 100
 227 ms 960 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 15 ms 528 KB Output is correct
5 Correct 45 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 604 KB Output is correct
2 Correct 90 ms 616 KB Output is correct
3 Correct 121 ms 604 KB Output is correct
4 Correct 203 ms 600 KB Output is correct
5 Correct 206 ms 728 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 604 KB Output is correct
2 Correct 103 ms 600 KB Output is correct
3 Correct 120 ms 600 KB Output is correct
4 Correct 93 ms 600 KB Output is correct
5 Correct 110 ms 600 KB Output is correct
6 Correct 102 ms 604 KB Output is correct
7 Correct 126 ms 604 KB Output is correct
8 Correct 101 ms 600 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 348 KB Output is correct
2 Correct 153 ms 640 KB Output is correct
3 Correct 121 ms 604 KB Output is correct
4 Correct 162 ms 640 KB Output is correct
5 Correct 156 ms 676 KB Output is correct
6 Correct 199 ms 600 KB Output is correct
7 Correct 165 ms 604 KB Output is correct
8 Correct 136 ms 600 KB Output is correct
9 Correct 136 ms 600 KB Output is correct
10 Correct 183 ms 604 KB Output is correct
11 Correct 155 ms 600 KB Output is correct
12 Correct 126 ms 600 KB Output is correct
13 Correct 172 ms 604 KB Output is correct
14 Correct 146 ms 604 KB Output is correct
15 Correct 176 ms 604 KB Output is correct
16 Correct 101 ms 600 KB Output is correct
17 Correct 208 ms 720 KB Output is correct
18 Correct 149 ms 672 KB Output is correct
19 Correct 185 ms 960 KB Output is correct
20 Correct 139 ms 644 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 652 KB Output is correct
2 Correct 141 ms 600 KB Output is correct
3 Correct 147 ms 604 KB Output is correct
4 Correct 162 ms 604 KB Output is correct
5 Correct 136 ms 600 KB Output is correct
6 Correct 198 ms 604 KB Output is correct
7 Correct 170 ms 604 KB Output is correct
8 Correct 170 ms 600 KB Output is correct
9 Correct 164 ms 600 KB Output is correct
10 Correct 138 ms 848 KB Output is correct
11 Correct 183 ms 604 KB Output is correct
12 Correct 157 ms 600 KB Output is correct
13 Correct 145 ms 620 KB Output is correct
14 Correct 142 ms 620 KB Output is correct
15 Correct 150 ms 600 KB Output is correct
16 Correct 102 ms 596 KB Output is correct
17 Correct 227 ms 852 KB Output is correct
18 Correct 145 ms 600 KB Output is correct