oj.uz

Submission #93681

# Submission time Handle Problem Language Result Execution time Memory
93681 2019-01-10T16:52:06 Z antimirage Highway Tolls (IOI18_highway) C++14
12 / 100
 197 ms 32668 KB 
#include "highway.h"
#include <bits/stdc++.h>
//#include "grader.cpp"

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

using namespace std;

const int QWE = 1e5 + 5;

int n, m, a, b, h[QWE];
long long len;
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 2572 KB Output is correct
2 Correct 4 ms 2676 KB Output is correct
3 Correct 4 ms 2552 KB Output is correct
4 Correct 4 ms 2672 KB Output is correct
5 Correct 4 ms 2552 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2552 KB Output is correct
9 Correct 4 ms 2552 KB Output is correct
10 Correct 1 ms 2600 KB Output is correct
11 Correct 5 ms 2680 KB Output is correct
12 Correct 4 ms 2656 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2836 KB Output is correct
2 Correct 22 ms 3572 KB Output is correct
3 Correct 187 ms 11552 KB Output is correct
4 Correct 186 ms 11600 KB Output is correct
5 Correct 182 ms 11544 KB Output is correct
6 Correct 191 ms 11516 KB Output is correct
7 Correct 167 ms 11560 KB Output is correct
8 Correct 178 ms 11556 KB Output is correct
9 Correct 169 ms 11544 KB Output is correct
10 Correct 196 ms 11508 KB Output is correct
11 Correct 173 ms 13316 KB Output is correct
12 Correct 174 ms 14504 KB Output is correct
13 Correct 185 ms 13664 KB Output is correct
14 Correct 197 ms 12656 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4796 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 2808 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 68 ms 32592 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 62 ms 32668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -