oj.uz

Submission #414627

# Submission time Handle Problem Language Result Execution time Memory
414627 2021-05-30T18:35:52 Z schse Highway Tolls (IOI18_highway) C++17
100 / 100
 279 ms 11624 KB 
#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <cassert>
#include <bits/stdc++.h>
using namespace std;

struct node
{
  vector<pair<int, int>> edges; // to number;
  bool been = false;
  int depth;
};

vector<node> g;
std::vector<int> w;
long long lastanswer = 0;
/*
vector<int> maketree(int root, vector<int> U, vector<int> V) //returns translation layer
{

  for (int i = 0; i < g.size(); i++)
    g[i].been = false;
  vector<int> trans;
  queue<pair<int, int>> q; // node depth;
  q.push({root, 0});
  g[root].been = true;
  while (!q.empty())
  {
    auto p = q.front();
    q.pop();
    g[p.first].depth = p.second;
    for (auto i : g[p.first].edges)
    {
      if (g[i.first].been)
        continue;
      g[i.first].been = true;
      trans.push_back(i.second);
      q.push({i.first, p.second + 1});
    }
  }
  return trans;
}
*/
pair<vector<int>, vector<int>> maketwotrees(int rootU, int rootV, int edgeon)
{
  for (int i = 0; i < g.size(); i++)
    g[i].been = false;
  vector<int> rootedinU;
  vector<int> rootedinV;
  rootedinV.push_back(edgeon);
  rootedinU.push_back(edgeon);
  queue<tuple<int, int, bool>> q; // node depth;
  q.push({rootU, 0, false});
  q.push({rootV, 0, true});
  g[rootU].been = true;
  g[rootV].been = true;
  while (!q.empty())
  {
    auto [to, depth, from] = q.front();
    q.pop();
    g[to].depth = depth;
    for (auto i : g[to].edges)
    {
      if (g[i.first].been)
        continue;
      g[i.first].been = true;
      (from ? rootedinV : rootedinU).push_back(i.second);
      q.push({i.first, depth + 1, from});
    }
  }
  return {rootedinU, rootedinV};
}

int binarysearnew(vector<int> translation, vector<int> inactive)
{
  // trans translation
  int b = 0;
  int e = translation.size();
  while (b + 1 != e)
  {
    fill(w.begin(), w.end(), 1);
    for (int x : inactive)
      w[x] = 0;
    for (int x : translation)
      w[x] = 0;
    for (int i = (b + e) / 2; i < e; i++)
      w[translation[i]] = 1;
    long long tmp = ask(w);
    if (tmp != lastanswer)
      b = (b + e) / 2;
    else
      e = (b + e) / 2;
  }
  return translation[b];
}
/*
int binarysear(vector<int> translation)
{
  // trans translation
  int b = 0;
  int e = translation.size();
  while (b + 1 != e)
  {
    fill(w.begin(), w.end(), 1);
    for (int x : translation)
      w[x] = 0;

    for (int i = (b + e) / 2; i < e; i++)
      w[translation[i]] = 1;
    long long tmp = ask(w);
    if (tmp != lastanswer)
      b = (b + e) / 2;
    else
      e = (b + e) / 2;
  }
  return translation[b];
}
*/
int binarysearPoints()
{
  int b = 0;
  int e = w.size();
  fill(w.begin(), w.end(), 0);
  while (b + 1 != e)
  {
    for (int i = (b + e) / 2; i < e; i++)
      w[i] = 1;
    long long tmp = ask(w);
    if (tmp != lastanswer)
    {
      for (int i = (b + e) / 2; i < e; i++)
        w[i] = 0;
      b = (b + e) / 2;
    }
    else
      e = (b + e) / 2;
  }
  return b;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
  int M = U.size();
  vector<int> inorderbfs(M);
  g.resize(N);
  w.resize(M);
  for (int i = 0; i < U.size(); i++) // rebuild graph
  {
    g[U[i]].edges.push_back({V[i], i});
    g[V[i]].edges.push_back({U[i], i});
  }

  fill(w.begin(), w.end(), 0);
  lastanswer = ask(w);

  //Punkt auf Pfad
  int edgeonpath = binarysearPoints();

  auto [Utranslation, Vtranslation] = maketwotrees(U[edgeonpath], V[edgeonpath],edgeonpath); // rooted in

  // 1.Endpunkt
  //inorderbfs = maketree(edgeinpath, U, V);
  int endpointa, endpointb;
  if (!Utranslation.empty())
  {
    int tmp = binarysearnew(Utranslation, Vtranslation);
    endpointa = V[tmp];
    if (g[U[tmp]].depth >= g[V[tmp]].depth)
      endpointa = U[tmp];
    assert(endpointa != -1);
  }
  else
    endpointa = V[edgeonpath];

  //2. Endpunkt
  //inorderbfs = maketree(endpointa, U, V);
  if (!Vtranslation.empty())
  {
    int tmp = binarysearnew(Vtranslation, Utranslation);
    //tmp = binarysear(inorderbfs);
    endpointb = U[tmp];
    if (g[V[tmp]].depth >= g[U[tmp]].depth)
      endpointb = V[tmp];
  }
  else
    endpointa = U[edgeonpath];

  answer(endpointa, endpointb);
}

Compilation message

highway.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > maketwotrees(int, int, int)':
highway.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i = 0; i < g.size(); i++)
      |                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:149:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   for (int i = 0; i < U.size(); i++) // rebuild graph
      |                   ~~^~~~~~~~~~
highway.cpp:190:9: warning: 'endpointb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  190 |   answer(endpointa, endpointb);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 2 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 13 ms 1224 KB Output is correct
3 Correct 131 ms 9556 KB Output is correct
4 Correct 129 ms 9436 KB Output is correct
5 Correct 167 ms 9452 KB Output is correct
6 Correct 154 ms 9436 KB Output is correct
7 Correct 174 ms 9516 KB Output is correct
8 Correct 148 ms 9496 KB Output is correct
9 Correct 180 ms 9496 KB Output is correct
10 Correct 140 ms 9532 KB Output is correct
11 Correct 179 ms 8760 KB Output is correct
12 Correct 195 ms 8860 KB Output is correct
13 Correct 129 ms 8864 KB Output is correct
14 Correct 133 ms 8756 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1224 KB Output is correct
2 Correct 34 ms 2320 KB Output is correct
3 Correct 38 ms 3128 KB Output is correct
4 Correct 157 ms 8700 KB Output is correct
5 Correct 160 ms 8752 KB Output is correct
6 Correct 100 ms 8764 KB Output is correct
7 Correct 159 ms 8756 KB Output is correct
8 Correct 159 ms 8828 KB Output is correct
9 Correct 157 ms 8796 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 18 ms 1256 KB Output is correct
3 Correct 94 ms 7408 KB Output is correct
4 Correct 176 ms 9460 KB Output is correct
5 Correct 160 ms 9544 KB Output is correct
6 Correct 148 ms 9432 KB Output is correct
7 Correct 123 ms 9432 KB Output is correct
8 Correct 126 ms 9480 KB Output is correct
9 Correct 170 ms 9492 KB Output is correct
10 Correct 123 ms 9600 KB Output is correct
11 Correct 158 ms 8772 KB Output is correct
12 Correct 121 ms 8808 KB Output is correct
13 Correct 139 ms 8880 KB Output is correct
14 Correct 181 ms 8748 KB Output is correct
15 Correct 122 ms 9512 KB Output is correct
16 Correct 171 ms 9516 KB Output is correct
17 Correct 136 ms 8884 KB Output is correct
18 Correct 139 ms 8888 KB Output is correct
19 Correct 171 ms 9464 KB Output is correct
20 Correct 179 ms 8788 KB Output is correct
21 Correct 150 ms 10640 KB Output is correct
22 Correct 153 ms 10480 KB Output is correct
23 Correct 123 ms 9972 KB Output is correct
24 Correct 151 ms 9908 KB Output is correct
25 Correct 167 ms 9016 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1456 KB Output is correct
2 Correct 16 ms 1312 KB Output is correct
3 Correct 204 ms 10016 KB Output is correct
4 Correct 213 ms 10424 KB Output is correct
5 Correct 279 ms 11488 KB Output is correct
6 Correct 194 ms 11488 KB Output is correct
7 Correct 243 ms 11592 KB Output is correct
8 Correct 251 ms 11480 KB Output is correct
9 Correct 146 ms 7832 KB Output is correct
10 Correct 217 ms 7860 KB Output is correct
11 Correct 229 ms 8852 KB Output is correct
12 Correct 202 ms 10572 KB Output is correct
13 Correct 205 ms 10988 KB Output is correct
14 Correct 275 ms 11504 KB Output is correct
15 Correct 200 ms 11480 KB Output is correct
16 Correct 233 ms 8908 KB Output is correct
17 Correct 133 ms 10172 KB Output is correct
18 Correct 131 ms 10360 KB Output is correct
19 Correct 160 ms 10400 KB Output is correct
20 Correct 128 ms 10308 KB Output is correct
21 Correct 219 ms 11288 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1352 KB Output is correct
2 Correct 16 ms 1436 KB Output is correct
3 Correct 144 ms 9956 KB Output is correct
4 Correct 212 ms 10248 KB Output is correct
5 Correct 174 ms 10376 KB Output is correct
6 Correct 191 ms 11608 KB Output is correct
7 Correct 194 ms 9964 KB Output is correct
8 Correct 164 ms 10148 KB Output is correct
9 Correct 198 ms 10476 KB Output is correct
10 Correct 265 ms 11412 KB Output is correct
11 Correct 204 ms 11612 KB Output is correct
12 Correct 262 ms 11468 KB Output is correct
13 Correct 226 ms 8816 KB Output is correct
14 Correct 215 ms 7928 KB Output is correct
15 Correct 228 ms 8804 KB Output is correct
16 Correct 153 ms 7856 KB Output is correct
17 Correct 218 ms 8816 KB Output is correct
18 Correct 217 ms 8036 KB Output is correct
19 Correct 183 ms 10512 KB Output is correct
20 Correct 266 ms 10980 KB Output is correct
21 Correct 266 ms 11492 KB Output is correct
22 Correct 269 ms 11624 KB Output is correct
23 Correct 234 ms 11476 KB Output is correct
24 Correct 273 ms 11532 KB Output is correct
25 Correct 232 ms 11572 KB Output is correct
26 Correct 204 ms 11584 KB Output is correct
27 Correct 126 ms 10308 KB Output is correct
28 Correct 173 ms 10152 KB Output is correct
29 Correct 139 ms 10440 KB Output is correct
30 Correct 132 ms 10272 KB Output is correct
31 Correct 143 ms 10216 KB Output is correct
32 Correct 154 ms 10184 KB Output is correct
33 Correct 131 ms 10364 KB Output is correct
34 Correct 125 ms 10216 KB Output is correct
35 Correct 163 ms 10176 KB Output is correct
36 Correct 176 ms 10176 KB Output is correct
37 Correct 131 ms 10380 KB Output is correct
38 Correct 175 ms 10264 KB Output is correct
39 Correct 216 ms 11460 KB Output is correct
40 Correct 218 ms 11376 KB Output is correct
41 Correct 267 ms 11416 KB Output is correct
42 Correct 221 ms 11408 KB Output is correct