oj.uz

Submission #1013702

# Submission time Handle Problem Language Result Execution time Memory
1013702 2024-07-03T21:42:31 Z MarwenElarbi Highway Tolls (IOI18_highway) C++17
90 / 100
 172 ms 13588 KB 
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
/*
namespace {

constexpr int MAX_NUM_CALLS = 100;
constexpr long long INF = 1LL << 61;

int N, M, A, B, S, T;
std::vector<int> U, V;
std::vector<std::vector<std::pair<int, int>>> graph;

bool answered, wrong_pair;
int num_calls;

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

void wrong_answer(const char *MSG) {
  printf("Wrong Answer: %s\n", MSG);
  exit(0);
}

}  // namespace

long long ask(const std::vector<int> &w) {
  if (++num_calls > MAX_NUM_CALLS) {
    wrong_answer("more than 100 calls to ask");
  }
  if (w.size() != (size_t)M) {
    wrong_answer("w is invalid");
  }
  for (size_t i = 0; i < w.size(); ++i) {
    if (!(w[i] == 0 || w[i] == 1)) {
      wrong_answer("w is invalid");
    }
  }

  std::vector<bool> visited(N, false);
  std::vector<long long> current_dist(N, INF);
  std::queue<int> qa, qb;
  qa.push(S);
  current_dist[S] = 0;
  while (!qa.empty() || !qb.empty()) {
    int v;
    if (qb.empty() ||
        (!qa.empty() && current_dist[qa.front()] <= current_dist[qb.front()])) {
      v = qa.front();
      qa.pop();
    } else {
      v = qb.front();
      qb.pop();
    }
    if (visited[v]) {
      continue;
    }
    visited[v] = true;
    long long d = current_dist[v];
    if (v == T) {
      return d;
    }
    for (auto e : graph[v]) {
      int vv = e.first;
      int ei = e.second;
      if (!visited[vv]) {
        if (w[ei] == 0) {
          if (current_dist[vv] > d + A) {
            current_dist[vv] = d + A;
            qa.push(vv);
          }
        } else {
          if (current_dist[vv] > d + B) {
            current_dist[vv] = d + B;
            qb.push(vv);
          }
        }
      }
    }
  }
  return -1;
}

void answer(int s, int t) {
  if (answered) {
    wrong_answer("answered not exactly once");
  }

  if (!((s == S && t == T) || (s == T && t == S))) {
    wrong_pair = true;
  }

  answered = true;
}*/
const int nax=130000;
vector<pair<int,int>> adj[nax];
int dis[nax];
vector<int> on(nax);
long long m,n,init;
vector<bool> vis(nax);
int bfs(int x){
  for (int i = 0; i < n; ++i)
  {
    dis[i]=1e9;
    vis[i]=0;
  }
  queue<int> q;
  q.push(x);
  dis[x]=0;
  while(!q.empty()){
    int node=q.front();
    q.pop();
    if(vis[node]) continue;
    vis[x]=true;
    for(auto u:adj[node]){
      if(dis[u.fi]<=dis[node]+1) continue;
      q.push(u.fi);
      dis[u.fi]=dis[node]+1;
    }
  }
  vector<pair<int,int>> cur;
  for (int i = 0; i < n; ++i)
  {
    cur.pb({dis[i],i});
  }
  sort(cur.begin(),cur.end(),greater<pair<int,int>>());
  int l=0;
  int r=cur.size();
  while(r-l>1){
    int mid=(r+l)/2;
    for (int i = 0; i < on.size(); ++i) on[i]=0;
    for (int i = 0; i < mid; ++i)
    {
      for(auto u:adj[cur[i].se]) on[u.se]=1;
    }
    if(ask(on)==init) l=mid;
    else r=mid;
  }
  return cur[l].se;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n=N;
    m=U.size();
    vector<int> cnt;
    on.resize(U.size(),0);
    for (int i = 0; i < U.size(); ++i)
    {
      cnt.pb(0);
    }
    init=ask(cnt);
    for (int i = 0; i < U.size(); ++i)
    {
      adj[U[i]].pb({V[i],i});
      adj[V[i]].pb({U[i],i});
    }
    int S=bfs(bfs(2));
    answer(S,bfs(S));
}
/*
int main() {
  #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
  N = read_int();
  M = read_int();
  A = read_int();
  B = read_int();
  S = read_int();
  T = read_int();
  U.resize(M);
  V.resize(M);
  graph.assign(N, std::vector<std::pair<int, int>>());
  for (int i = 0; i < M; ++i) {
    U[i] = read_int();
    V[i] = read_int();
    graph[U[i]].push_back({V[i], i});
    graph[V[i]].push_back({U[i], i});
  }

  answered = false;
  wrong_pair = false;
  num_calls = 0;
  find_pair(N, U, V, A, B);
  if (!answered) {
    wrong_answer("answered not exactly once");
  }
  if (wrong_pair) {
    wrong_answer("{s, t} is wrong");
  }
  printf("Accepted: %d\n", num_calls);
  return 0;
}
*/

Compilation message

highway.cpp: In function 'int bfs(int)':
highway.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i < on.size(); ++i) on[i]=0;
      |                     ~~^~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0; i < U.size(); ++i)
      |                     ~~^~~~~~~~~~
highway.cpp:162:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |     for (int i = 0; i < U.size(); ++i)
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 13 ms 5128 KB Output is correct
3 Correct 127 ms 11428 KB Output is correct
4 Correct 130 ms 11424 KB Output is correct
5 Correct 138 ms 11424 KB Output is correct
6 Correct 123 ms 11408 KB Output is correct
7 Correct 146 ms 11668 KB Output is correct
8 Correct 153 ms 11424 KB Output is correct
9 Correct 133 ms 11700 KB Output is correct
10 Correct 123 ms 11424 KB Output is correct
11 Correct 137 ms 10884 KB Output is correct
12 Correct 142 ms 10836 KB Output is correct
13 Correct 140 ms 10836 KB Output is correct
14 Correct 121 ms 10844 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5128 KB Output is correct
2 Correct 19 ms 5856 KB Output is correct
3 Correct 28 ms 6464 KB Output is correct
4 Correct 98 ms 10880 KB Output is correct
5 Correct 89 ms 10840 KB Output is correct
6 Correct 75 ms 10828 KB Output is correct
7 Correct 75 ms 10876 KB Output is correct
8 Correct 83 ms 10840 KB Output is correct
9 Correct 91 ms 10840 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 13 ms 5208 KB Output is correct
3 Correct 114 ms 10144 KB Output is correct
4 Correct 140 ms 11412 KB Output is correct
5 Correct 133 ms 11420 KB Output is correct
6 Correct 158 ms 11432 KB Output is correct
7 Correct 135 ms 11424 KB Output is correct
8 Correct 139 ms 11864 KB Output is correct
9 Correct 115 ms 11380 KB Output is correct
10 Correct 148 ms 11420 KB Output is correct
11 Correct 122 ms 10840 KB Output is correct
12 Correct 131 ms 10840 KB Output is correct
13 Correct 130 ms 10848 KB Output is correct
14 Correct 124 ms 10836 KB Output is correct
15 Correct 143 ms 11724 KB Output is correct
16 Correct 119 ms 11428 KB Output is correct
17 Correct 133 ms 10852 KB Output is correct
18 Correct 132 ms 10836 KB Output is correct
19 Correct 144 ms 11440 KB Output is correct
20 Correct 129 ms 10844 KB Output is correct
21 Correct 102 ms 11668 KB Output is correct
22 Correct 102 ms 11664 KB Output is correct
23 Correct 102 ms 11824 KB Output is correct
24 Correct 100 ms 11584 KB Output is correct
25 Correct 114 ms 11316 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5208 KB Output is correct
2 Correct 16 ms 5208 KB Output is correct
3 Correct 136 ms 11784 KB Output is correct
4 Correct 138 ms 12248 KB Output is correct
5 Correct 164 ms 13468 KB Output is correct
6 Correct 148 ms 13208 KB Output is correct
7 Correct 169 ms 13200 KB Output is correct
8 Correct 134 ms 13188 KB Output is correct
9 Correct 104 ms 10488 KB Output is correct
10 Correct 116 ms 11080 KB Output is correct
11 Correct 100 ms 11856 KB Output is correct
12 Correct 148 ms 12836 KB Output is correct
13 Correct 155 ms 13008 KB Output is correct
14 Correct 146 ms 13224 KB Output is correct
15 Correct 160 ms 13472 KB Output is correct
16 Correct 128 ms 11704 KB Output is correct
17 Correct 95 ms 11720 KB Output is correct
18 Correct 101 ms 11904 KB Output is correct
19 Correct 98 ms 11820 KB Output is correct
20 Correct 105 ms 12132 KB Output is correct
21 Correct 172 ms 13196 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5240 KB Output is correct
2 Correct 12 ms 5208 KB Output is correct
3 Correct 129 ms 11828 KB Output is correct
4 Correct 138 ms 11988 KB Output is correct
5 Correct 129 ms 12252 KB Output is correct
6 Correct 144 ms 13456 KB Output is correct
7 Partially correct 127 ms 11996 KB Output is partially correct
8 Partially correct 134 ms 11976 KB Output is partially correct
9 Partially correct 140 ms 12264 KB Output is partially correct
10 Partially correct 168 ms 13196 KB Output is partially correct
11 Partially correct 142 ms 13184 KB Output is partially correct
12 Partially correct 147 ms 13176 KB Output is partially correct
13 Correct 109 ms 11560 KB Output is correct
14 Correct 94 ms 11016 KB Output is correct
15 Correct 112 ms 11540 KB Output is correct
16 Correct 96 ms 11104 KB Output is correct
17 Correct 115 ms 11564 KB Output is correct
18 Correct 101 ms 11004 KB Output is correct
19 Partially correct 144 ms 12828 KB Output is partially correct
20 Correct 161 ms 13172 KB Output is correct
21 Correct 143 ms 13220 KB Output is correct
22 Partially correct 148 ms 13212 KB Output is partially correct
23 Partially correct 145 ms 13588 KB Output is partially correct
24 Correct 166 ms 13236 KB Output is correct
25 Partially correct 160 ms 13220 KB Output is partially correct
26 Correct 148 ms 13240 KB Output is correct
27 Partially correct 103 ms 12084 KB Output is partially correct
28 Partially correct 92 ms 11764 KB Output is partially correct
29 Partially correct 93 ms 11992 KB Output is partially correct
30 Partially correct 103 ms 12008 KB Output is partially correct
31 Correct 93 ms 11816 KB Output is correct
32 Correct 94 ms 11868 KB Output is correct
33 Correct 94 ms 12272 KB Output is correct
34 Correct 108 ms 11780 KB Output is correct
35 Partially correct 92 ms 11756 KB Output is partially correct
36 Partially correct 92 ms 11716 KB Output is partially correct
37 Partially correct 91 ms 11988 KB Output is partially correct
38 Partially correct 91 ms 11868 KB Output is partially correct
39 Partially correct 172 ms 13188 KB Output is partially correct
40 Correct 168 ms 13204 KB Output is correct
41 Correct 141 ms 13184 KB Output is correct
42 Correct 170 ms 13496 KB Output is correct