oj.uz

Submission #965489

# Submission time Handle Problem Language Result Execution time Memory
965489 2024-04-18T18:13:40 Z FEDIKUS Highway Tolls (IOI18_highway) C++17
90 / 100
 171 ms 11344 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn=90010;

vector<pair<int,int> > g[maxn];

int uradi(int n,int m,int a,int b,ll bez,int prva,int pocetak,vector<int> &u,vector<int> &v){
  queue<int> bfs;
  bfs.push(pocetak);
  vector<bool> posetio(n,0);
  posetio[pocetak]=true;

  vector<int> redosled;
  vector<int> intime(n,0);
  int t=0;

  while(!bfs.empty()){
    int node=bfs.front();
    intime[node]=t++;
    bfs.pop();

    for(auto [u,ind]:g[node]){
      if(posetio[u]) continue;
      if(ind<prva) continue;
      posetio[u]=true;
      bfs.push(u);
      redosled.push_back(ind);
    }
  }

  int l=0;
  int r=int(redosled.size())-1; // ?
  int ret=-1;
  while(l<=r){
    int mid=l+(r-l)/2;

    vector<int> w(m,1);
    for(int i=0;i<mid;i++){
      w[redosled[i]]=0;
    }
    if(ask(w)>bez){
      ret=mid;
      l=mid+1;
    }else r=mid-1;
  }

  if(intime[u[redosled[ret]]]>intime[v[redosled[ret]]]){
    return u[redosled[ret]];
  }else return v[redosled[ret]];
}

void find_pair(int n,vector<int> u,vector<int> v,int a,int b) {
  int m=u.size();
  int prva=0;
  int l=1,r=m;
  ll bez=ask(vector<int>(m,0));
  while(l<=r){
    int mid=l+(r-l)/2;
    vector<int> w(m,0);
    fill(w.begin(),w.begin()+mid,1);
    if(ask(w)>bez){
      prva=mid;
      r=mid-1;
    }else l=mid+1;
  }

  prva--;

  for(int i=0;i<m;i++){
    g[u[i]].push_back({v[i],i});
    g[v[i]].push_back({u[i],i});
  }

  int lik1=uradi(n,m,a,b,bez,prva,u[prva],u,v);
  int lik2=uradi(n,m,a,b,bez,prva,lik1,u,v);

  answer(lik1,lik2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2568 KB Output is correct
2 Correct 10 ms 3256 KB Output is correct
3 Correct 85 ms 8952 KB Output is correct
4 Correct 136 ms 8972 KB Output is correct
5 Correct 96 ms 9032 KB Output is correct
6 Correct 98 ms 9004 KB Output is correct
7 Correct 98 ms 8704 KB Output is correct
8 Correct 115 ms 9032 KB Output is correct
9 Correct 106 ms 9056 KB Output is correct
10 Correct 90 ms 8800 KB Output is correct
11 Correct 72 ms 8068 KB Output is correct
12 Correct 105 ms 7976 KB Output is correct
13 Correct 117 ms 8452 KB Output is correct
14 Correct 109 ms 8228 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3192 KB Output is correct
2 Correct 28 ms 3884 KB Output is correct
3 Correct 32 ms 4224 KB Output is correct
4 Correct 92 ms 8256 KB Output is correct
5 Correct 96 ms 7980 KB Output is correct
6 Correct 71 ms 8148 KB Output is correct
7 Correct 87 ms 7620 KB Output is correct
8 Correct 76 ms 8044 KB Output is correct
9 Correct 73 ms 7708 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2576 KB Output is correct
2 Correct 10 ms 3316 KB Output is correct
3 Correct 85 ms 7388 KB Output is correct
4 Correct 91 ms 8480 KB Output is correct
5 Correct 83 ms 8044 KB Output is correct
6 Correct 66 ms 8272 KB Output is correct
7 Correct 95 ms 8812 KB Output is correct
8 Correct 71 ms 8240 KB Output is correct
9 Correct 143 ms 9156 KB Output is correct
10 Correct 94 ms 8764 KB Output is correct
11 Correct 111 ms 8364 KB Output is correct
12 Correct 90 ms 8216 KB Output is correct
13 Correct 90 ms 8280 KB Output is correct
14 Correct 102 ms 7936 KB Output is correct
15 Correct 95 ms 8300 KB Output is correct
16 Correct 95 ms 8036 KB Output is correct
17 Correct 94 ms 7984 KB Output is correct
18 Correct 99 ms 8000 KB Output is correct
19 Correct 72 ms 8040 KB Output is correct
20 Correct 81 ms 7540 KB Output is correct
21 Correct 104 ms 8916 KB Output is correct
22 Correct 89 ms 8432 KB Output is correct
23 Correct 86 ms 9256 KB Output is correct
24 Correct 96 ms 8676 KB Output is correct
25 Correct 92 ms 8332 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3284 KB Output is correct
2 Correct 18 ms 3552 KB Output is correct
3 Correct 108 ms 8912 KB Output is correct
4 Correct 111 ms 9564 KB Output is correct
5 Correct 133 ms 11088 KB Output is correct
6 Correct 135 ms 10916 KB Output is correct
7 Correct 118 ms 10664 KB Output is correct
8 Correct 163 ms 10632 KB Output is correct
9 Correct 91 ms 8080 KB Output is correct
10 Correct 157 ms 8996 KB Output is correct
11 Correct 164 ms 9256 KB Output is correct
12 Correct 115 ms 10500 KB Output is correct
13 Correct 171 ms 10732 KB Output is correct
14 Correct 165 ms 11160 KB Output is correct
15 Correct 145 ms 11156 KB Output is correct
16 Correct 116 ms 9700 KB Output is correct
17 Correct 120 ms 9000 KB Output is correct
18 Correct 66 ms 8816 KB Output is correct
19 Correct 119 ms 9428 KB Output is correct
20 Correct 100 ms 9072 KB Output is correct
21 Correct 135 ms 10404 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3284 KB Output is correct
2 Correct 16 ms 3308 KB Output is correct
3 Correct 99 ms 9404 KB Output is correct
4 Correct 127 ms 9064 KB Output is correct
5 Partially correct 97 ms 9496 KB Output is partially correct
6 Partially correct 125 ms 11312 KB Output is partially correct
7 Partially correct 96 ms 9144 KB Output is partially correct
8 Partially correct 122 ms 9180 KB Output is partially correct
9 Correct 130 ms 9388 KB Output is correct
10 Correct 121 ms 11296 KB Output is correct
11 Partially correct 131 ms 11132 KB Output is partially correct
12 Partially correct 151 ms 10852 KB Output is partially correct
13 Correct 101 ms 8828 KB Output is correct
14 Correct 90 ms 8816 KB Output is correct
15 Correct 121 ms 9488 KB Output is correct
16 Correct 89 ms 9172 KB Output is correct
17 Correct 99 ms 9292 KB Output is correct
18 Correct 109 ms 8980 KB Output is correct
19 Correct 139 ms 10524 KB Output is correct
20 Correct 168 ms 10544 KB Output is correct
21 Correct 128 ms 11344 KB Output is correct
22 Partially correct 168 ms 10912 KB Output is partially correct
23 Partially correct 124 ms 10760 KB Output is partially correct
24 Partially correct 143 ms 11160 KB Output is partially correct
25 Correct 134 ms 10672 KB Output is correct
26 Partially correct 121 ms 10884 KB Output is partially correct
27 Correct 122 ms 8824 KB Output is correct
28 Correct 85 ms 9112 KB Output is correct
29 Correct 82 ms 9684 KB Output is correct
30 Partially correct 113 ms 9500 KB Output is partially correct
31 Correct 84 ms 9168 KB Output is correct
32 Correct 95 ms 9344 KB Output is correct
33 Partially correct 125 ms 9408 KB Output is partially correct
34 Correct 94 ms 9092 KB Output is correct
35 Correct 82 ms 8848 KB Output is correct
36 Partially correct 83 ms 9708 KB Output is partially correct
37 Correct 85 ms 9472 KB Output is correct
38 Correct 124 ms 9756 KB Output is correct
39 Correct 140 ms 10848 KB Output is correct
40 Correct 120 ms 10628 KB Output is correct
41 Partially correct 135 ms 10836 KB Output is partially correct
42 Correct 148 ms 10624 KB Output is correct