oj.uz

Submission #965488

# Submission time Handle Problem Language Result Execution time Memory
965488 2024-04-18T18:11:50 Z FEDIKUS Highway Tolls (IOI18_highway) C++17
23 / 100
 194 ms 11576 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 2 ms 2552 KB Output is correct
2 Correct 1 ms 2556 KB Output is correct
3 Correct 1 ms 2548 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 2552 KB Output is correct
7 Correct 1 ms 2548 KB Output is correct
8 Correct 1 ms 2548 KB Output is correct
9 Correct 1 ms 2804 KB Output is correct
10 Correct 1 ms 2552 KB Output is correct
11 Correct 2 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 2576 KB Output is correct
2 Correct 16 ms 3228 KB Output is correct
3 Correct 103 ms 9044 KB Output is correct
4 Correct 104 ms 9040 KB Output is correct
5 Correct 99 ms 8816 KB Output is correct
6 Correct 99 ms 8588 KB Output is correct
7 Correct 111 ms 9024 KB Output is correct
8 Correct 95 ms 8820 KB Output is correct
9 Correct 87 ms 9164 KB Output is correct
10 Correct 122 ms 8820 KB Output is correct
11 Correct 95 ms 8264 KB Output is correct
12 Correct 96 ms 8464 KB Output is correct
13 Correct 123 ms 8240 KB Output is correct
14 Incorrect 82 ms 8256 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 11 ms 3172 KB Output is correct
2 Correct 18 ms 3812 KB Output is correct
3 Correct 23 ms 4468 KB Output is correct
4 Correct 70 ms 8020 KB Output is correct
5 Correct 69 ms 8008 KB Output is correct
6 Correct 68 ms 8148 KB Output is correct
7 Correct 91 ms 8224 KB Output is correct
8 Correct 83 ms 8520 KB Output is correct
9 Incorrect 86 ms 8004 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 13 ms 3260 KB Output is correct
3 Correct 65 ms 7376 KB Output is correct
4 Correct 87 ms 8804 KB Output is correct
5 Correct 76 ms 9020 KB Output is correct
6 Correct 78 ms 9152 KB Output is correct
7 Correct 103 ms 8752 KB Output is correct
8 Correct 78 ms 8580 KB Output is correct
9 Incorrect 89 ms 8628 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 13 ms 3264 KB Output is correct
2 Correct 18 ms 3316 KB Output is correct
3 Correct 119 ms 8900 KB Output is correct
4 Correct 144 ms 9756 KB Output is correct
5 Correct 153 ms 11576 KB Output is correct
6 Correct 151 ms 10920 KB Output is correct
7 Correct 129 ms 10908 KB Output is correct
8 Correct 130 ms 11332 KB Output is correct
9 Correct 148 ms 8572 KB Output is correct
10 Correct 96 ms 9356 KB Output is correct
11 Correct 152 ms 9972 KB Output is correct
12 Correct 114 ms 10308 KB Output is correct
13 Correct 122 ms 10952 KB Output is correct
14 Correct 171 ms 11156 KB Output is correct
15 Correct 194 ms 10952 KB Output is correct
16 Correct 147 ms 9676 KB Output is correct
17 Correct 119 ms 9556 KB Output is correct
18 Correct 88 ms 9704 KB Output is correct
19 Correct 94 ms 9468 KB Output is correct
20 Correct 80 ms 9564 KB Output is correct
21 Correct 116 ms 10228 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3260 KB Output is correct
2 Correct 12 ms 3304 KB Output is correct
3 Correct 102 ms 8940 KB Output is correct
4 Correct 96 ms 9080 KB Output is correct
5 Correct 108 ms 9764 KB Output is correct
6 Partially correct 161 ms 11356 KB Output is partially correct
7 Partially correct 92 ms 9364 KB Output is partially correct
8 Partially correct 114 ms 9304 KB Output is partially correct
9 Partially correct 109 ms 9548 KB Output is partially correct
10 Partially correct 153 ms 11364 KB Output is partially correct
11 Partially correct 135 ms 11156 KB Output is partially correct
12 Partially correct 123 ms 11108 KB Output is partially correct
13 Correct 114 ms 9488 KB Output is correct
14 Correct 123 ms 9148 KB Output is correct
15 Correct 111 ms 9300 KB Output is correct
16 Correct 99 ms 9268 KB Output is correct
17 Correct 130 ms 9952 KB Output is correct
18 Correct 131 ms 9400 KB Output is correct
19 Correct 163 ms 10520 KB Output is correct
20 Correct 115 ms 10968 KB Output is correct
21 Partially correct 135 ms 10928 KB Output is partially correct
22 Partially correct 180 ms 11144 KB Output is partially correct
23 Partially correct 127 ms 10976 KB Output is partially correct
24 Partially correct 161 ms 10884 KB Output is partially correct
25 Partially correct 149 ms 11124 KB Output is partially correct
26 Correct 163 ms 10904 KB Output is correct
27 Partially correct 104 ms 9512 KB Output is partially correct
28 Correct 94 ms 9548 KB Output is correct
29 Partially correct 83 ms 9684 KB Output is partially correct
30 Incorrect 89 ms 9284 KB Output is incorrect: {s, t} is wrong.
31 Halted 0 ms 0 KB -