oj.uz

Submission #93680

# Submission time Handle Problem Language Result Execution time Memory
93680 2019-01-10T16:47:56 Z antimirage Highway Tolls (IOI18_highway) C++14
5 / 100
 216 ms 32608 KB 
#include "highway.h"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back

using namespace std;

const int QWE = 1e5 + 5;

int n, len, m, a, b, h[QWE];
vector < vector <pair <int, int> > > g;
vector <int> w, u1, u2;

vector <int> vec[QWE];

void dfs (int v, int level = 0, int p = -1)
{
    h[v] = level;
    for (auto to : g[v])
    {
      if (to.fr == p) continue;
      vec[level + 1].pb(to.sc);
      dfs(to.fr, level + 1, v);
    }
}

int Find(int root)
{
  dfs(root);
  int l = -1, r = vec[len / a].size() - 1;

  while (r - l > 1)
  {
    int md = (l + r) >> 1;
    for (int i = 0; i < m; i++)
      w[i] = 0;
    for (int i = 0; i <= md; i++)
      w[ vec[len / a][i] ] = 1;

    if ( ask(w) != len )
      r = md;
    else
      l = md;
  }
  if ( h[ u1[ vec[len / a][r] ] ] > h[ u2[ vec[len / a][r] ] ] )
      return u1[ vec[len / a][r] ];

  return u2[ vec[len / a][r] ];
}

void find_pair(int  N, std::vector<int> U, std::vector<int> V, int A, int B)
{
  u1 = U;
  u2 = V;
  a = A;
  b = B;
  n = N;
  g.resize(n + 1);

  m = U.size();
  for (int j = 0; j < m; ++j)
  {
    w.pb(0);
    g[ U[j] ].pb( mk( V[j], j) );
    g[ V[j] ].pb( mk( U[j], j) );
  }
  len = ask(w);

  answer( 0, Find(0) );
}
/**
4 3 1 3 0 3
0 1
0 2
0 3
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2672 KB Output is correct
2 Correct 4 ms 2552 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2600 KB Output is correct
5 Correct 4 ms 2684 KB Output is correct
6 Correct 4 ms 2672 KB Output is correct
7 Correct 4 ms 2552 KB Output is correct
8 Correct 4 ms 2556 KB Output is correct
9 Correct 4 ms 2676 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct
11 Correct 4 ms 2676 KB Output is correct
12 Correct 4 ms 2552 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2840 KB Output is correct
2 Correct 16 ms 3572 KB Output is correct
3 Correct 189 ms 11544 KB Output is correct
4 Correct 172 ms 11604 KB Output is correct
5 Correct 183 ms 11548 KB Output is correct
6 Correct 181 ms 11516 KB Output is correct
7 Correct 185 ms 11752 KB Output is correct
8 Correct 145 ms 11560 KB Output is correct
9 Correct 160 ms 11644 KB Output is correct
10 Correct 216 ms 11532 KB Output is correct
11 Correct 199 ms 13372 KB Output is correct
12 Correct 194 ms 14556 KB Output is correct
13 Correct 189 ms 13596 KB Output is correct
14 Incorrect 205 ms 12652 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 4788 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2680 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 32608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 65 ms 32608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -