oj.uz

Submission #1010358

# Submission time Handle Problem Language Result Execution time Memory
1010358 2024-06-28T23:42:29 Z HappyCapybara Highway Tolls (IOI18_highway) C++17
51 / 100
 101 ms 11424 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  vector<vector<pair<int,int>>> g(N);
  for (int i=0; i<M; i++){
    g[U[i]].push_back({V[i], i});
    g[V[i]].push_back({U[i], i});
  }

  vector<int> f(M, 0);
  ll d = ask(f)/A;

  vector<bool> seen(N, false);
  seen[0] = true;
  queue<int> q;
  vector<vector<pair<int,int>>> v;
  for (pair<int,int> next : g[0]){
    vector<pair<int,int>> x;
    x.push_back(next);
    q.push(next.first);
    seen[next.first] = true;
    while (!q.empty()){
      int cur = q.front();
      q.pop();
      for (pair<int,int> neigh : g[cur]){
        if (seen[neigh.first]) continue;
        seen[neigh.first] = true;
        x.push_back(neigh);
        q.push(neigh.first);
      }
    }
    v.push_back(x);
  }

  int l = 0, r = v.size();
  while (l != r-1){
    int m = (l+r)/2;
    vector<int> w(M, 0);
    for (int i=l; i<m; i++){
      for (pair<int,int> p : v[i]) w[p.second] = 1;
    }
    if (ask(w) > d*A) r = m;
    else l = m;
  }

  int br = l;
  l = 0; r = v[br].size();
  while (l != r-1){
    int m = (l+r)/2;
    vector<int> w(M, 0);
    for (int i=m; i<r; i++) w[v[br][i].second] = 1;
    if (ask(w) > d*A) l = m;
    else r = m;
  }

  int S = v[br][l].first;

  vector<int> dist(N, -1);
  q.push(S);
  dist[S] = 0;
  vector<pair<int,int>> pos;
  while (!q.empty()){
    int cur = q.front();
    q.pop();
    for (pair<int,int> next : g[cur]){
      if (dist[next.first] != -1) continue;
      dist[next.first] = dist[cur]+1;
      if (dist[next.first] == d) pos.push_back(next);
      else q.push(next.first);
    }
  }
  l = 0; r = pos.size();
  while (l != r-1){
    int m = (l+r)/2;
    vector<int> w(M, 0);
    for (int i=l; i<m; i++) w[pos[i].second] = 1;
    if (ask(w) > d*A) r = m;
    else l = m;
  }
  answer(S, pos[l].first);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 9 ms 1280 KB Output is correct
3 Correct 78 ms 9324 KB Output is correct
4 Correct 72 ms 9192 KB Output is correct
5 Correct 72 ms 9208 KB Output is correct
6 Correct 68 ms 9200 KB Output is correct
7 Correct 80 ms 9360 KB Output is correct
8 Correct 88 ms 9188 KB Output is correct
9 Correct 74 ms 9448 KB Output is correct
10 Correct 67 ms 9184 KB Output is correct
11 Correct 73 ms 8432 KB Output is correct
12 Correct 75 ms 8512 KB Output is correct
13 Correct 70 ms 8644 KB Output is correct
14 Correct 68 ms 8484 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1368 KB Output is correct
2 Correct 13 ms 2244 KB Output is correct
3 Correct 20 ms 3104 KB Output is correct
4 Correct 62 ms 8648 KB Output is correct
5 Correct 57 ms 8644 KB Output is correct
6 Correct 57 ms 8644 KB Output is correct
7 Correct 60 ms 8644 KB Output is correct
8 Correct 61 ms 8644 KB Output is correct
9 Correct 72 ms 8656 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 1368 KB Output is correct
3 Correct 67 ms 7252 KB Output is correct
4 Correct 75 ms 9196 KB Output is correct
5 Correct 84 ms 9204 KB Output is correct
6 Correct 68 ms 9244 KB Output is correct
7 Correct 66 ms 9212 KB Output is correct
8 Correct 71 ms 9148 KB Output is correct
9 Correct 75 ms 9212 KB Output is correct
10 Correct 72 ms 9224 KB Output is correct
11 Correct 75 ms 8504 KB Output is correct
12 Correct 71 ms 8428 KB Output is correct
13 Correct 72 ms 8304 KB Output is correct
14 Correct 67 ms 8648 KB Output is correct
15 Correct 63 ms 9420 KB Output is correct
16 Correct 66 ms 9208 KB Output is correct
17 Correct 67 ms 8412 KB Output is correct
18 Correct 75 ms 8544 KB Output is correct
19 Correct 68 ms 9444 KB Output is correct
20 Correct 66 ms 8652 KB Output is correct
21 Correct 67 ms 10972 KB Output is correct
22 Correct 56 ms 10752 KB Output is correct
23 Correct 62 ms 9608 KB Output is correct
24 Correct 62 ms 9560 KB Output is correct
25 Correct 73 ms 8676 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1368 KB Output is correct
2 Correct 8 ms 1368 KB Output is correct
3 Correct 76 ms 9976 KB Output is correct
4 Correct 89 ms 10468 KB Output is correct
5 Incorrect 101 ms 11424 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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