oj.uz

Submission #965485

# Submission time Handle Problem Language Result Execution time Memory
965485 2024-04-18T18:03:37 Z FEDIKUS Highway Tolls (IOI18_highway) C++17
5 / 100
 122 ms 8952 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=0;
  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 2552 KB Output is correct
2 Correct 1 ms 2552 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 2548 KB Output is correct
7 Correct 1 ms 2552 KB Output is correct
8 Correct 1 ms 2552 KB Output is correct
9 Correct 1 ms 2552 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 2 ms 2548 KB Output is correct
12 Correct 1 ms 2544 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2572 KB Output is correct
2 Correct 10 ms 3236 KB Output is correct
3 Correct 120 ms 8488 KB Output is correct
4 Correct 88 ms 8468 KB Output is correct
5 Correct 77 ms 8544 KB Output is correct
6 Correct 77 ms 8952 KB Output is correct
7 Correct 81 ms 8688 KB Output is correct
8 Correct 80 ms 8784 KB Output is correct
9 Correct 73 ms 8452 KB Output is correct
10 Correct 67 ms 8812 KB Output is correct
11 Correct 70 ms 7592 KB Output is correct
12 Correct 122 ms 8196 KB Output is correct
13 Correct 85 ms 7992 KB Output is correct
14 Incorrect 69 ms 8224 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 Runtime error 11 ms 5844 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3024 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 14 ms 3020 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -