oj.uz

Submission #965482

# Submission time Handle Problem Language Result Execution time Memory
965482 2024-04-18T18:01:50 Z FEDIKUS Highway Tolls (IOI18_highway) C++17
23 / 100
 175 ms 11380 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

const int maxn=90010;

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

int uradi(int n,int m,int a,int b,int 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;
  int 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 2556 KB Output is correct
2 Correct 1 ms 2556 KB Output is correct
3 Correct 1 ms 2556 KB Output is correct
4 Correct 1 ms 2552 KB Output is correct
5 Correct 1 ms 2548 KB Output is correct
6 Correct 1 ms 2548 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2548 KB Output is correct
9 Correct 2 ms 2552 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 2552 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2568 KB Output is correct
2 Correct 14 ms 3248 KB Output is correct
3 Correct 120 ms 8928 KB Output is correct
4 Correct 88 ms 8724 KB Output is correct
5 Correct 130 ms 9040 KB Output is correct
6 Correct 85 ms 9148 KB Output is correct
7 Correct 102 ms 8700 KB Output is correct
8 Correct 84 ms 8584 KB Output is correct
9 Correct 80 ms 8476 KB Output is correct
10 Correct 121 ms 9088 KB Output is correct
11 Correct 72 ms 7596 KB Output is correct
12 Correct 86 ms 8200 KB Output is correct
13 Correct 127 ms 8220 KB Output is correct
14 Incorrect 82 ms 8140 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3160 KB Output is correct
2 Correct 17 ms 4264 KB Output is correct
3 Correct 23 ms 4528 KB Output is correct
4 Correct 79 ms 7964 KB Output is correct
5 Correct 76 ms 8668 KB Output is correct
6 Correct 79 ms 8172 KB Output is correct
7 Correct 83 ms 7544 KB Output is correct
8 Correct 70 ms 7996 KB Output is correct
9 Incorrect 107 ms 8132 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2572 KB Output is correct
2 Correct 14 ms 3232 KB Output is correct
3 Correct 59 ms 7860 KB Output is correct
4 Correct 91 ms 8720 KB Output is correct
5 Correct 93 ms 8256 KB Output is correct
6 Correct 92 ms 8500 KB Output is correct
7 Correct 99 ms 8696 KB Output is correct
8 Correct 93 ms 8096 KB Output is correct
9 Incorrect 86 ms 8816 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3272 KB Output is correct
2 Correct 18 ms 3304 KB Output is correct
3 Correct 122 ms 9120 KB Output is correct
4 Correct 115 ms 9652 KB Output is correct
5 Correct 151 ms 10624 KB Output is correct
6 Correct 167 ms 11100 KB Output is correct
7 Correct 115 ms 11272 KB Output is correct
8 Correct 137 ms 11068 KB Output is correct
9 Correct 129 ms 8080 KB Output is correct
10 Correct 86 ms 9004 KB Output is correct
11 Correct 148 ms 9460 KB Output is correct
12 Correct 115 ms 10276 KB Output is correct
13 Correct 114 ms 11204 KB Output is correct
14 Correct 151 ms 11144 KB Output is correct
15 Correct 127 ms 11292 KB Output is correct
16 Correct 108 ms 10096 KB Output is correct
17 Correct 83 ms 8996 KB Output is correct
18 Correct 73 ms 8584 KB Output is correct
19 Correct 101 ms 9336 KB Output is correct
20 Correct 91 ms 9336 KB Output is correct
21 Correct 112 ms 10624 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3272 KB Output is correct
2 Correct 12 ms 3296 KB Output is correct
3 Correct 127 ms 9328 KB Output is correct
4 Correct 134 ms 9300 KB Output is correct
5 Partially correct 93 ms 9712 KB Output is partially correct
6 Partially correct 148 ms 11096 KB Output is partially correct
7 Partially correct 128 ms 9416 KB Output is partially correct
8 Partially correct 125 ms 9536 KB Output is partially correct
9 Correct 104 ms 9476 KB Output is correct
10 Correct 113 ms 10848 KB Output is correct
11 Partially correct 175 ms 11140 KB Output is partially correct
12 Partially correct 120 ms 10860 KB Output is partially correct
13 Correct 124 ms 8872 KB Output is correct
14 Correct 116 ms 8916 KB Output is correct
15 Correct 159 ms 9296 KB Output is correct
16 Correct 132 ms 8940 KB Output is correct
17 Correct 160 ms 9300 KB Output is correct
18 Correct 112 ms 9148 KB Output is correct
19 Correct 150 ms 10744 KB Output is correct
20 Correct 129 ms 10516 KB Output is correct
21 Correct 134 ms 10916 KB Output is correct
22 Partially correct 123 ms 10924 KB Output is partially correct
23 Partially correct 135 ms 11380 KB Output is partially correct
24 Partially correct 141 ms 11108 KB Output is partially correct
25 Correct 147 ms 10684 KB Output is correct
26 Partially correct 136 ms 10708 KB Output is partially correct
27 Correct 94 ms 9228 KB Output is correct
28 Correct 102 ms 9108 KB Output is correct
29 Correct 104 ms 9700 KB Output is correct
30 Incorrect 85 ms 9392 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -