oj.uz

Submission #597793

# Submission time Handle Problem Language Result Execution time Memory
597793 2022-07-16T22:02:16 Z TimDee Highway Tolls (IOI18_highway) C++14
51 / 100
 195 ms 13220 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
  int m=u.size();
  vector<int> scuza(m,1); vector<int> paiu;
  ll dist = ask(scuza)/b;
  vector<vector<pair<int,int>>> adj(n);
  for (int i=0; i<m; ++i) {
    adj[u[i]].push_back({v[i],i});
    adj[v[i]].push_back({u[i],i});
  }
  vector<int> vis(n,0), d(n,0); vis[0]=1;
  vector<int> edges;
  queue<int> q; q.push(0);
  while (!q.empty()) {
    int u=q.front(); q.pop();
    for (auto it:adj[u]) {
      int v=it.first;
      if (!vis[v]) {
        vis[v]=1;
        d[v]=d[u]+1;
        edges.push_back(it.second);
        q.push(v);
      }
    }
  }
  int l=0, r=edges.size()-1;
  while (l<r) {
    int mid=(l+r)>>1;
    paiu=scuza;
    for (int i=0; i<=mid; ++i) paiu[edges[i]]=0;
    ll x = ask(paiu);
    if (x<1ll*dist*b) r=mid;
    else l=mid+1;
  }
  int bgn;
  if (d[u[edges[r]]]<d[v[edges[r]]]) bgn = u[edges[r]];
  else bgn = v[edges[r]];
  d.assign(n,0);
  vis.assign(n,0);
  vis[bgn]=1;
  q.push(bgn);
  edges.clear();
  while (!q.empty()) {
    int u=q.front(); q.pop();
    for (auto it:adj[u]) {
      int v=it.first;
      if (!vis[v]) {
        vis[v]=1;
        d[v]=d[u]+1;
        edges.push_back(it.second);
        q.push(v);
      }
    }
  }
  l=0,r=edges.size()-1;
  while (l<r) {
    int mid=(l+r)>>1;
    paiu=scuza;
    for (int i=0; i<=mid; ++i) paiu[edges[i]]=0;
    ll x = ask(paiu);
    if (x>1ll*dist*a) l=mid+1;
    else r=mid;
  }
  int s = d[u[edges[r]]]>d[v[edges[r]]] ? u[edges[r]] : v[edges[r]];
  d.assign(n,0);
  vis.assign(n,0);
  vis[s]=1;
  q.push(s);
  vector<vector<int>>D(n);
  while (!q.empty()) {
    int u=q.front(); q.pop();
    for (auto it:adj[u]) {
      int v=it.first;
      if (!vis[v]) {
        vis[v]=1;
        d[v]=d[u]+1;
        D[d[v]].push_back(v);
        q.push(v);
      }
    }
  }
  vector<int>amog=D[dist];
  l=0, r=amog.size()-1;
  while (l<r) {
    int mid=(l+r)>>1;
    paiu=scuza;
    for (int i=0; i<=mid; ++i) for (auto it:adj[amog[i]]) {
      int v=it.first;
      if (d[v]==d[amog[i]]-1) paiu[it.second]=0;
    }
    ll x = ask(paiu);
    if (x<1ll*dist*b) r=mid;
    else l=mid+1;
  } //cout<<s<<' '<<amog[r]<<'\n';
  answer(s,amog[r]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 400 KB Output is correct
2 Correct 14 ms 1424 KB Output is correct
3 Correct 150 ms 11600 KB Output is correct
4 Correct 141 ms 11604 KB Output is correct
5 Correct 165 ms 11612 KB Output is correct
6 Correct 182 ms 11576 KB Output is correct
7 Correct 163 ms 11600 KB Output is correct
8 Correct 160 ms 11544 KB Output is correct
9 Correct 119 ms 11620 KB Output is correct
10 Correct 130 ms 11596 KB Output is correct
11 Correct 158 ms 11336 KB Output is correct
12 Correct 146 ms 11696 KB Output is correct
13 Correct 118 ms 11392 KB Output is correct
14 Correct 147 ms 11452 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1748 KB Output is correct
2 Correct 23 ms 2972 KB Output is correct
3 Correct 41 ms 4488 KB Output is correct
4 Correct 131 ms 12016 KB Output is correct
5 Correct 103 ms 12296 KB Output is correct
6 Correct 147 ms 12808 KB Output is correct
7 Correct 100 ms 13140 KB Output is correct
8 Correct 153 ms 12324 KB Output is correct
9 Correct 130 ms 12660 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 14 ms 1572 KB Output is correct
3 Correct 112 ms 9072 KB Output is correct
4 Correct 149 ms 11552 KB Output is correct
5 Correct 128 ms 11608 KB Output is correct
6 Correct 129 ms 11560 KB Output is correct
7 Correct 166 ms 11552 KB Output is correct
8 Correct 130 ms 11544 KB Output is correct
9 Correct 141 ms 11708 KB Output is correct
10 Correct 148 ms 11596 KB Output is correct
11 Correct 122 ms 11396 KB Output is correct
12 Correct 185 ms 11284 KB Output is correct
13 Correct 127 ms 11440 KB Output is correct
14 Correct 131 ms 11608 KB Output is correct
15 Correct 152 ms 11572 KB Output is correct
16 Correct 162 ms 11548 KB Output is correct
17 Correct 129 ms 11392 KB Output is correct
18 Correct 125 ms 11520 KB Output is correct
19 Correct 126 ms 11564 KB Output is correct
20 Correct 145 ms 11620 KB Output is correct
21 Correct 136 ms 12828 KB Output is correct
22 Correct 119 ms 12732 KB Output is correct
23 Correct 160 ms 12304 KB Output is correct
24 Correct 141 ms 12216 KB Output is correct
25 Correct 195 ms 13220 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1480 KB Output is correct
2 Incorrect 18 ms 1628 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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