oj.uz

Submission #475140

# Submission time Handle Problem Language Result Execution time Memory
475140 2021-09-21T09:42:34 Z cs71107 Highway Tolls (IOI18_highway) C++14
100 / 100
 307 ms 12432 KB 
#include "highway.h"

#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 2e5+10;

vector<vector<pii> > graph;

int upar[MAXN];
int ud[MAXN];
int uque[MAXN];

int vpar[MAXN];
int vd[MAXN];
int vque[MAXN];

int chk[MAXN];

int uver[MAXN];
int vver[MAXN];


void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  int M = U.size();

  vector<int> w(M,0);

  const ll shortest_path = ask(w);
  ll cur_path = 0;

  int idx = 0;

  for(int i=16;i>=0;i--){

    if((idx|(1<<i))>=M)continue;

    for(int j=0;j<(idx|(1<<i));j++){
      w[j] = 1;
    }
    for(int j=(idx|(1<<i));j<M;j++){
      w[j] = 0;
    }

    cur_path = ask(w);

    if(!(shortest_path^cur_path)){
      idx|=(1<<i);
    }
  }

  int u = U[idx];
  int v = V[idx];

  graph = vector<vector<pii> > (N);

  for(int i=0;i<M;i++){
    graph[U[i]].push_back(pii(V[i],i));
    graph[V[i]].push_back(pii(U[i],i));
  }

  fill(ud,ud+N,-1);
  fill(upar,upar+N,-1);
  fill(vd,vd+N,-1);
  fill(vpar,vpar+N,-1);

  int L = 0;
  int R = 0;

  int here,there;

  ud[u] = 0;
  uque[0] = u;

  while(L<=R){
    here = uque[L]; L++;
    
    for(int i=0;i<(int)graph[here].size();i++){
      there = graph[here][i].f;
      if(ud[there]!=-1)continue;
      ud[there] = ud[here]+1;
      upar[there] = graph[here][i].s;
      R++;
      uque[R] = there;
    }
  }

  assert(R==(N-1));

  vd[v] = 0;
  vque[0] = v;

  L = 0;
  R = 0;

  while(L<=R){
    here = vque[L]; L++;
    
    for(int i=0;i<(int)graph[here].size();i++){
      there = graph[here][i].f;
      if(vd[there]!=-1)continue;
      vd[there] = vd[here]+1;
      vpar[there] = graph[here][i].s;
      R++;
      vque[R] = there;
    }
  }

  assert(R==(N-1));

  chk[idx] = 1;

  int cntu = 0,cntv = 0;

  uver[0] = u;

  for(int i=1;i<N;i++){
    here = uque[i];
    if(ud[here]<vd[here]){
      chk[upar[here]] = 1;
      cntu++;
      uver[cntu] = here;
    }
  }

  vver[0] = v;

  for(int i=1;i<N;i++){
    here = vque[i];
    if(vd[here]<ud[here]){
      chk[vpar[here]] = 1;
      cntv++;
      vver[cntv] = here;
    }
  }

  for(int i=0;i<M;i++){
    w[i] = chk[i]^1;
  }

  int idu = 0;

  for(int t=16;t>=0;t--){

    if((idu|(1<<t))>cntu)continue;

    for(int i=idu|(1<<t);i<=cntu;i++){
      here = uver[i];
      w[upar[here]] = 1;
    }

    cur_path = ask(w);

    if(cur_path^shortest_path){
      idu|=(1<<t);
    }

    for(int i=idu|(1<<t);i<=cntu;i++){
      here = uver[i];
      w[upar[here]] = 0;
    }
  }

  int idv = 0;

  for(int t=16;t>=0;t--){

    if((idv|(1<<t))>cntv)continue;

    for(int i=idv|(1<<t);i<=cntv;i++){
      here = vver[i];
      w[vpar[here]] = 1;
    }

    cur_path = ask(w);

    if(cur_path^shortest_path){
      idv|=(1<<t);
    }

    for(int i=idv|(1<<t);i<=cntv;i++){
      here = vver[i];
      w[vpar[here]] = 0;
    }
  }

  int anss = uver[idu];
  int anst = vver[idv];

  answer(anss,anst);

  return;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 16 ms 1344 KB Output is correct
3 Correct 149 ms 10488 KB Output is correct
4 Correct 190 ms 10404 KB Output is correct
5 Correct 183 ms 10388 KB Output is correct
6 Correct 182 ms 10484 KB Output is correct
7 Correct 203 ms 10484 KB Output is correct
8 Correct 190 ms 10428 KB Output is correct
9 Correct 205 ms 10404 KB Output is correct
10 Correct 161 ms 10444 KB Output is correct
11 Correct 228 ms 9872 KB Output is correct
12 Correct 210 ms 9936 KB Output is correct
13 Correct 209 ms 9940 KB Output is correct
14 Correct 194 ms 9844 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1388 KB Output is correct
2 Correct 26 ms 2360 KB Output is correct
3 Correct 47 ms 3568 KB Output is correct
4 Correct 159 ms 9852 KB Output is correct
5 Correct 130 ms 9848 KB Output is correct
6 Correct 171 ms 9912 KB Output is correct
7 Correct 152 ms 9852 KB Output is correct
8 Correct 170 ms 9952 KB Output is correct
9 Correct 116 ms 9848 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 16 ms 1392 KB Output is correct
3 Correct 159 ms 8184 KB Output is correct
4 Correct 217 ms 10428 KB Output is correct
5 Correct 226 ms 10640 KB Output is correct
6 Correct 168 ms 10392 KB Output is correct
7 Correct 199 ms 10404 KB Output is correct
8 Correct 222 ms 10396 KB Output is correct
9 Correct 210 ms 10400 KB Output is correct
10 Correct 190 ms 10504 KB Output is correct
11 Correct 193 ms 9964 KB Output is correct
12 Correct 171 ms 9948 KB Output is correct
13 Correct 231 ms 9952 KB Output is correct
14 Correct 165 ms 9872 KB Output is correct
15 Correct 159 ms 10492 KB Output is correct
16 Correct 208 ms 10408 KB Output is correct
17 Correct 172 ms 9884 KB Output is correct
18 Correct 201 ms 9952 KB Output is correct
19 Correct 161 ms 10408 KB Output is correct
20 Correct 197 ms 9912 KB Output is correct
21 Correct 173 ms 10644 KB Output is correct
22 Correct 111 ms 10600 KB Output is correct
23 Correct 157 ms 10608 KB Output is correct
24 Correct 175 ms 10480 KB Output is correct
25 Correct 148 ms 9964 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1392 KB Output is correct
2 Correct 19 ms 1436 KB Output is correct
3 Correct 189 ms 10772 KB Output is correct
4 Correct 203 ms 11220 KB Output is correct
5 Correct 230 ms 12240 KB Output is correct
6 Correct 269 ms 12432 KB Output is correct
7 Correct 260 ms 12400 KB Output is correct
8 Correct 303 ms 12280 KB Output is correct
9 Correct 229 ms 7904 KB Output is correct
10 Correct 144 ms 8100 KB Output is correct
11 Correct 161 ms 8984 KB Output is correct
12 Correct 254 ms 11000 KB Output is correct
13 Correct 284 ms 11704 KB Output is correct
14 Correct 293 ms 12320 KB Output is correct
15 Correct 285 ms 12316 KB Output is correct
16 Correct 174 ms 9132 KB Output is correct
17 Correct 136 ms 10632 KB Output is correct
18 Correct 197 ms 10988 KB Output is correct
19 Correct 129 ms 10760 KB Output is correct
20 Correct 165 ms 10916 KB Output is correct
21 Correct 230 ms 12376 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1388 KB Output is correct
2 Correct 21 ms 1480 KB Output is correct
3 Correct 274 ms 10880 KB Output is correct
4 Correct 184 ms 10960 KB Output is correct
5 Correct 260 ms 11280 KB Output is correct
6 Correct 294 ms 12308 KB Output is correct
7 Correct 179 ms 10828 KB Output is correct
8 Correct 192 ms 10996 KB Output is correct
9 Correct 221 ms 11200 KB Output is correct
10 Correct 247 ms 12288 KB Output is correct
11 Correct 253 ms 12212 KB Output is correct
12 Correct 242 ms 12380 KB Output is correct
13 Correct 158 ms 8996 KB Output is correct
14 Correct 148 ms 8184 KB Output is correct
15 Correct 205 ms 8996 KB Output is correct
16 Correct 180 ms 8292 KB Output is correct
17 Correct 171 ms 8992 KB Output is correct
18 Correct 153 ms 8220 KB Output is correct
19 Correct 241 ms 11080 KB Output is correct
20 Correct 220 ms 11652 KB Output is correct
21 Correct 307 ms 12264 KB Output is correct
22 Correct 280 ms 12208 KB Output is correct
23 Correct 257 ms 12312 KB Output is correct
24 Correct 222 ms 12288 KB Output is correct
25 Correct 289 ms 12244 KB Output is correct
26 Correct 243 ms 12252 KB Output is correct
27 Correct 157 ms 10780 KB Output is correct
28 Correct 161 ms 10688 KB Output is correct
29 Correct 192 ms 10956 KB Output is correct
30 Correct 169 ms 10788 KB Output is correct
31 Correct 144 ms 10780 KB Output is correct
32 Correct 189 ms 10652 KB Output is correct
33 Correct 182 ms 10896 KB Output is correct
34 Correct 198 ms 10800 KB Output is correct
35 Correct 183 ms 10728 KB Output is correct
36 Correct 209 ms 10628 KB Output is correct
37 Correct 191 ms 10884 KB Output is correct
38 Correct 124 ms 10852 KB Output is correct
39 Correct 235 ms 12388 KB Output is correct
40 Correct 224 ms 12416 KB Output is correct
41 Correct 251 ms 12376 KB Output is correct
42 Correct 225 ms 12380 KB Output is correct