oj.uz

Submission #465419

# Submission time Handle Problem Language Result Execution time Memory
465419 2021-08-16T02:14:26 Z MatheusLealV Highway Tolls (IOI18_highway) C++17
90 / 100
 406 ms 20184 KB 
#include "highway.h"
#define f first
#define ss second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define N 90005
vector<int> caras,especiais;
vector<pii> grafo[N], tree[N];
int pai[N], n, m, id_pai[N],A,B, dist_st,contador=0;
void dfs(int x, int p){
	pai[x]=p;
	caras.pb(x);
	for(auto v: tree[x]){
		if(v.f == p) continue;
		id_pai[v.f] =v.ss;
		dfs(v.f, x);
	}
}

int get(int root){
  caras.clear();
  dfs(root,root);
  int ini = 1, fim = sz(caras)-1,mid,best=-1;
  while(fim >=ini){
    mid = (ini + fim)/2;
    vector<int> w(m);
    for(int i=0;i<m;i++)w[i]=1;
    for(int i = 1; i <= mid; i++) w[id_pai[caras[i]]] = 0;
    int dmid = ask(w);contador++;
    if(dmid == A*dist_st){
      best=mid;
      fim=mid-1;
    }else ini=mid+1;
  }
  return caras[best];
}
void find_pair(int N_, std::vector<int> U, std::vector<int> V, int AA, int BB) {
  n=N_;A=AA;B=BB;m=sz(U);
  for(int i = 0; i < sz(U); i++){
  	grafo[U[i]].pb({V[i],i}); grafo[V[i]].pb({U[i],i});
  }
  vector<int>w(m);
  dist_st = ask(w)/A;contador++;
  int ini = 0, fim = n-1,mid,root=-1;
  while(fim>=ini){
    mid=(ini+fim)/2;
    vector<int> w(m);
    for(int i = 0; i < m; i++) w[i]=0;
    for(int x = 0; x <= mid; x++){
      for(auto v: grafo[x]) w[v.ss] = 1;
    }
    contador++;
    if(ask(w) != A*dist_st){
      root = mid;
      fim=mid-1;
    }
    else ini=mid+1;
  }
  assert(root!=-1);
  vector<int>vis(n), dist(n);
  queue<int>fila;
  fila.push(root); vis[root]=1;
  while(!fila.empty()){
    int x=fila.front();fila.pop();
    for(auto v: grafo[x]){
      if(!vis[v.f]){
        vis[v.f]=1;dist[v.f]=dist[x]+1;
        fila.push(v.f);
        tree[x].pb(v);
        tree[v.f].pb({x,v.ss});
        especiais.pb(v.ss);
      }
    }
  }

  int S = get(root);
  int T = get(S);
  answer(S, T);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4552 KB Output is correct
2 Correct 19 ms 5740 KB Output is correct
3 Correct 219 ms 15680 KB Output is correct
4 Correct 230 ms 15760 KB Output is correct
5 Correct 214 ms 15664 KB Output is correct
6 Correct 225 ms 15708 KB Output is correct
7 Correct 183 ms 15768 KB Output is correct
8 Correct 174 ms 15664 KB Output is correct
9 Correct 179 ms 15660 KB Output is correct
10 Correct 199 ms 15672 KB Output is correct
11 Correct 190 ms 16108 KB Output is correct
12 Correct 182 ms 16728 KB Output is correct
13 Correct 185 ms 16080 KB Output is correct
14 Correct 207 ms 16156 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6088 KB Output is correct
2 Correct 28 ms 7788 KB Output is correct
3 Correct 59 ms 9420 KB Output is correct
4 Correct 163 ms 18024 KB Output is correct
5 Correct 157 ms 18076 KB Output is correct
6 Correct 183 ms 19344 KB Output is correct
7 Correct 145 ms 19972 KB Output is correct
8 Correct 184 ms 18516 KB Output is correct
9 Correct 140 ms 20184 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4552 KB Output is correct
2 Correct 21 ms 5696 KB Output is correct
3 Correct 152 ms 13264 KB Output is correct
4 Correct 211 ms 15720 KB Output is correct
5 Correct 193 ms 15756 KB Output is correct
6 Correct 209 ms 15648 KB Output is correct
7 Correct 210 ms 15704 KB Output is correct
8 Correct 202 ms 15648 KB Output is correct
9 Correct 232 ms 15836 KB Output is correct
10 Correct 179 ms 15756 KB Output is correct
11 Correct 252 ms 15552 KB Output is correct
12 Correct 207 ms 16652 KB Output is correct
13 Correct 244 ms 16240 KB Output is correct
14 Correct 212 ms 16652 KB Output is correct
15 Correct 202 ms 15660 KB Output is correct
16 Correct 213 ms 15756 KB Output is correct
17 Correct 226 ms 15956 KB Output is correct
18 Correct 238 ms 16424 KB Output is correct
19 Correct 219 ms 15672 KB Output is correct
20 Correct 254 ms 16696 KB Output is correct
21 Correct 204 ms 16540 KB Output is correct
22 Correct 191 ms 16364 KB Output is correct
23 Correct 177 ms 16292 KB Output is correct
24 Correct 203 ms 16640 KB Output is correct
25 Correct 273 ms 19860 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5804 KB Output is correct
2 Correct 29 ms 5796 KB Output is correct
3 Correct 262 ms 15984 KB Output is correct
4 Correct 268 ms 16344 KB Output is correct
5 Correct 316 ms 17212 KB Output is correct
6 Correct 285 ms 17120 KB Output is correct
7 Correct 328 ms 17180 KB Output is correct
8 Correct 291 ms 17120 KB Output is correct
9 Correct 210 ms 12544 KB Output is correct
10 Correct 242 ms 12688 KB Output is correct
11 Correct 221 ms 13996 KB Output is correct
12 Correct 295 ms 15888 KB Output is correct
13 Correct 294 ms 16400 KB Output is correct
14 Correct 305 ms 16932 KB Output is correct
15 Correct 327 ms 16996 KB Output is correct
16 Correct 263 ms 13996 KB Output is correct
17 Correct 242 ms 16564 KB Output is correct
18 Correct 228 ms 16772 KB Output is correct
19 Correct 228 ms 16580 KB Output is correct
20 Correct 243 ms 16712 KB Output is correct
21 Correct 314 ms 17468 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5800 KB Output is correct
2 Correct 26 ms 5828 KB Output is correct
3 Partially correct 239 ms 16024 KB Output is partially correct
4 Partially correct 245 ms 16160 KB Output is partially correct
5 Partially correct 317 ms 16420 KB Output is partially correct
6 Partially correct 282 ms 17284 KB Output is partially correct
7 Partially correct 290 ms 16124 KB Output is partially correct
8 Correct 254 ms 16128 KB Output is correct
9 Partially correct 242 ms 16336 KB Output is partially correct
10 Correct 392 ms 17096 KB Output is correct
11 Correct 329 ms 17104 KB Output is correct
12 Correct 335 ms 17108 KB Output is correct
13 Correct 280 ms 14064 KB Output is correct
14 Correct 230 ms 12788 KB Output is correct
15 Correct 245 ms 13980 KB Output is correct
16 Correct 199 ms 12668 KB Output is correct
17 Correct 270 ms 14076 KB Output is correct
18 Correct 225 ms 12668 KB Output is correct
19 Correct 293 ms 16048 KB Output is correct
20 Correct 316 ms 16348 KB Output is correct
21 Partially correct 343 ms 16996 KB Output is partially correct
22 Correct 299 ms 16864 KB Output is correct
23 Partially correct 309 ms 16992 KB Output is partially correct
24 Partially correct 279 ms 16940 KB Output is partially correct
25 Correct 406 ms 16884 KB Output is correct
26 Partially correct 258 ms 16892 KB Output is partially correct
27 Partially correct 231 ms 16716 KB Output is partially correct
28 Partially correct 227 ms 16584 KB Output is partially correct
29 Partially correct 253 ms 16876 KB Output is partially correct
30 Correct 193 ms 16620 KB Output is correct
31 Correct 188 ms 16648 KB Output is correct
32 Correct 241 ms 16512 KB Output is correct
33 Correct 207 ms 16832 KB Output is correct
34 Correct 161 ms 16608 KB Output is correct
35 Partially correct 177 ms 16516 KB Output is partially correct
36 Partially correct 234 ms 16388 KB Output is partially correct
37 Correct 172 ms 16756 KB Output is correct
38 Correct 241 ms 16324 KB Output is correct
39 Partially correct 217 ms 17668 KB Output is partially correct
40 Correct 294 ms 17808 KB Output is correct
41 Partially correct 308 ms 17372 KB Output is partially correct
42 Correct 291 ms 17244 KB Output is correct