Submission #965494

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
965494	2024-04-18T18:21:27 Z	FEDIKUS	Highway Tolls (IOI18_highway)	C++17	6 / 100	90 ms	8200 KB

highway

#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,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> 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],v[prva],u,v);
  int lik2=uradi(n,m,a,b,bez,prva,v[prva],u[prva],u,v);

  answer(lik1,lik2);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2572 KB	Output is correct
2	Incorrect	8 ms	3164 KB	Output is incorrect: {s, t} is wrong.
3	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	3164 KB	Output is correct
2	Correct	15 ms	4024 KB	Output is correct
3	Correct	33 ms	4472 KB	Output is correct
4	Correct	89 ms	8200 KB	Output is correct
5	Correct	63 ms	7968 KB	Output is correct
6	Correct	86 ms	8076 KB	Output is correct
7	Correct	90 ms	7556 KB	Output is correct
8	Correct	78 ms	8128 KB	Output is correct
9	Correct	68 ms	7952 KB	Output is correct