oj.uz

Submission #965515

# Submission time Handle Problem Language Result Execution time Memory
965515 2024-04-18T18:47:51 Z FEDIKUS Highway Tolls (IOI18_highway) C++17
51 / 100
 126 ms 11392 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];
vector<pair<int,int> > g2[maxn];

int uradi(int n,int m,int a,int b,ll bez,int prva,int pocetak,int skoropocetak,vector<int> &u,vector<int> &v){
  queue<int> bfs;
  bfs.push(pocetak);
  vector<bool> posetio(n,0);
  posetio[pocetak]=true;
  for(auto i:g[pocetak]){
    if(i.first!=skoropocetak) posetio[i.first]=true;
  }

  vector<int> redosled;
  vector<int> cross;
  vector<int> intime(n,0);
  vector<int> parent(n,-1);
  int t=0;

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

    for(auto [u,ind]:g[node]){
      if(posetio[u] && u!=parent[node] && node!=pocetak){
        cross.push_back(ind);
        //cout<<"eo: "<<ind<<"\n";
        continue;
      }
      if(posetio[u]) continue;
      if(ind<prva) continue;
      posetio[u]=true;
      parent[u]=node;
      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,0);
    fill(w.begin(),w.begin()+prva,1);
    for(int i:cross) w[i]=1;
    for(int i=mid;i<int(redosled.size());i++){
      w[redosled[i]]=1;
    }
    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],v[prva],u,v);
  int lik2=uradi(n,m,a,b,bez,prva,v[prva],u[prva],u,v);

  //cout<<lik1<<" "<<lik2<<"\n";

  answer(lik1,lik2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4680 KB Output is correct
2 Correct 15 ms 5304 KB Output is correct
3 Correct 97 ms 11392 KB Output is correct
4 Correct 95 ms 11012 KB Output is correct
5 Correct 106 ms 11008 KB Output is correct
6 Correct 83 ms 10944 KB Output is correct
7 Correct 96 ms 10912 KB Output is correct
8 Correct 75 ms 11248 KB Output is correct
9 Correct 97 ms 11204 KB Output is correct
10 Correct 73 ms 11252 KB Output is correct
11 Correct 93 ms 10332 KB Output is correct
12 Correct 110 ms 10684 KB Output is correct
13 Correct 113 ms 10928 KB Output is correct
14 Correct 82 ms 10664 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5532 KB Output is correct
2 Correct 26 ms 5980 KB Output is correct
3 Correct 33 ms 6440 KB Output is correct
4 Correct 60 ms 10492 KB Output is correct
5 Correct 62 ms 10668 KB Output is correct
6 Correct 66 ms 10640 KB Output is correct
7 Correct 75 ms 10244 KB Output is correct
8 Correct 66 ms 10500 KB Output is correct
9 Correct 63 ms 10428 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4936 KB Output is correct
2 Correct 12 ms 5344 KB Output is correct
3 Correct 63 ms 9620 KB Output is correct
4 Correct 75 ms 11144 KB Output is correct
5 Correct 66 ms 10760 KB Output is correct
6 Correct 98 ms 10720 KB Output is correct
7 Correct 72 ms 11156 KB Output is correct
8 Correct 126 ms 10556 KB Output is correct
9 Correct 99 ms 11284 KB Output is correct
10 Correct 78 ms 11200 KB Output is correct
11 Correct 97 ms 10668 KB Output is correct
12 Correct 93 ms 10524 KB Output is correct
13 Correct 84 ms 10672 KB Output is correct
14 Correct 68 ms 10332 KB Output is correct
15 Correct 62 ms 10776 KB Output is correct
16 Correct 70 ms 10500 KB Output is correct
17 Correct 91 ms 10552 KB Output is correct
18 Correct 116 ms 10696 KB Output is correct
19 Correct 74 ms 10508 KB Output is correct
20 Correct 95 ms 9964 KB Output is correct
21 Correct 104 ms 11144 KB Output is correct
22 Correct 79 ms 10916 KB Output is correct
23 Correct 85 ms 11100 KB Output is correct
24 Correct 70 ms 11040 KB Output is correct
25 Correct 102 ms 10524 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5460 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 5672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -