oj.uz

Submission #965530

# Submission time Handle Problem Language Result Execution time Memory
965530 2024-04-18T19:34:36 Z FEDIKUS Highway Tolls (IOI18_highway) C++17
0 / 100
 16 ms 4052 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];
int intime[maxn];
bool posetio[maxn];
vector<int> nisu;
bool jesu[2*maxn];
vector<int> red1;
vector<int> red2;

void bfs(int n,int m,int prva,int poc1,int poc2){
  queue<pair<int,int> > bfs;
  bfs.push({poc1,poc1});
  bfs.push({poc2,poc2});
  posetio[poc1]=true;
  posetio[poc2]=true;
  red1.push_back(prva);
  red2.push_back(prva);
  jesu[prva]=true;

  int t=0;

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

    for(auto [u,ind]:g[node]){
      if(posetio[u]) continue;
      posetio[u]=true;
      bfs.push({u,odakle});

      if(odakle==poc1) red1.push_back(ind);
      else red2.push_back(ind);

      jesu[ind]=true;
    }
  }
  for(int i=0;i<m;i++) if(!jesu[i]) nisu.push_back(i);
}

bool bio[maxn];
set<int> tren;
vector<int> red;

int uradi(int n,int m,ll bez,int prva,int poc1,int poc2,vector<int> &u,vector<int> &v){
  int l=0;
  int r=int(red.size())-1; // ?
  int ret=-1;
  while(l<=r){
    int mid=l+(r-l)/2;

    vector<int> w(m,0);
    for(int i:nisu) w[i]=1;
    for(int i=mid;i<int(red.size());i++){
      w[red[i]]=1;
    }
    if(ask(w)>bez){
      ret=mid;
      l=mid+1;
    }else r=mid-1;
  }

  cout<<ret<<endl;

  if(ret==0) return poc2;

  if(intime[u[red[ret]]]>intime[v[red[ret]]]){
    return u[red[ret]];
  }else return v[red[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});
  }

  bfs(n,m,prva,u[prva],v[prva]);

  swap(red1,red2);

  red=red1;
  int lik1=uradi(n,m,bez,prva,u[prva],v[prva],u,v);
  red=red2;
  int lik2=uradi(n,m,bez,prva,v[prva],u[prva],u,v);

  answer(lik1,lik2);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 3096 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 3364 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3712 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 3160 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 4052 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 3792 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -