oj.uz

Submission #1026956

# Submission time Handle Problem Language Result Execution time Memory
1026956 2024-07-18T15:07:56 Z Malix Highway Tolls (IOI18_highway) C++14
12 / 100
 1500 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll MD=1e9+7;

void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
  int m = U.size();
  vi arr(m);
  REP(i,0,m)arr[i]=0;
  long long d=ask(arr)/A;
  vi p(n,0);
  vi val(n,-1);
  vector<vector<pi>> a(n);
  REP(i,0,m){
    a[U[i]].PB({V[i],i});
    a[V[i]].PB({U[i],i});
  }

  //bfs
  queue<int> pq;
  vi dist(n,-1);vi lf(n,1);
  pq.push(0);dist[0]=0;
  while(!pq.empty()){
    int k=pq.front();
    pq.pop();
    for(auto u:a[k]){
      if(p[k]==u.F)continue;
      lf[k]=0;
      dist[u.F]=dist[k]+1;
      p[u.F]=k;
      val[u.F]=u.S;
      pq.push(u.F);
    }
  }

  //find distance from bottom
  REP(i,0,n)if(p[i]==0)p[i]=i;
  vii parent(n,vi(log2(n)+3));
  REP(i,0,n)parent[i][0]=p[i];
  REP(j,1,log2(n)+2)REP(i,0,n)parent[i][j]=parent[parent[i][j-1]][j-1];
  
  vi bb;
  REP(i,1,n)if(lf[i]==1)bb.PB(i);
  int s=bb.size();
  int minv=dist[bb[0]],maxv=dist[bb[0]];
  REP(i,0,s){
    minv=min(minv,dist[bb[i]]);
    maxv=max(maxv,dist[bb[i]]);
  }
  int l=minv-maxv,r=n-1;
  while(l!=r){
    arr.clear();
    arr.resize(m,0);
    int mid=floor((l+r)/(double)2);
    REP(i,0,s){
      int e=mid+dist[bb[i]]-minv;
      if(e<0)continue;
      int q=bb[i];
      while(e>0){
        int f=LSOne(e);//cerr<<e<<" "<<f<<" "<<q<<"\n";
        q=parent[q][log2(f)];
        e-=f;
      }
      arr[val[q]]=1;
    }
      // for(auto u:arr)cerr<<u<<" ";
      // cerr<<"\n";
    if(ask(arr)>d*A)r=mid;
    else l=mid+1;
  }
  //find the node
  vi b;
  REP(i,0,s){
      int e=l+dist[bb[i]]-minv;
      if(e<0)continue;
      int q=bb[i];
      while(e>0){
        int f=LSOne(e);//cerr<<e<<" "<<f<<" "<<q<<"\n";
        q=parent[q][log2(f)];
        e-=f;
      }
      b.PB(q);
  }
  s=b.size();
  l=0,r=s-1;
  while(l!=r){
    arr.clear();
    arr.resize(m,0);
    int mid=(l+r)/2;
    REP(i,0,mid+1)arr[val[b[i]]]=1;
    if(ask(arr)>d*A)r=mid;
    else l=mid+1;
  }
  int ans1=b[l];

  //bfs again
  dist.clear();
  dist.resize(n,-1);
  pq.push(ans1);dist[ans1]=0;
  p.clear();
  p.resize(n,-1);
  val.clear();val.resize(n,-1);
  while(!pq.empty()){
    int k=pq.front();
    pq.pop();
    for(auto u:a[k]){
      if(p[k]==u.F)continue;
      dist[u.F]=dist[k]+1;
      p[u.F]=k;
      val[u.F]=u.S;
      pq.push(u.F);
    }
  }

  b.clear();
  REP(i,0,n)if(dist[i]==d)b.PB(i);
  s=b.size();
  l=0,r=s-1;
  while(l!=r){
    arr.clear();
    arr.resize(m,0);
    int mid=(l+r)/2;
    REP(i,0,mid+1)arr[val[b[i]]]=1;
    if(ask(arr)>d*A)r=mid;
    else l=mid+1;
  }
  // cerr<<ans1<<" "<<b[l];
  answer(ans1, b[l]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 12 ms 2484 KB Output is correct
3 Correct 165 ms 20080 KB Output is correct
4 Correct 151 ms 20032 KB Output is correct
5 Correct 158 ms 20260 KB Output is correct
6 Correct 157 ms 20040 KB Output is correct
7 Correct 156 ms 20132 KB Output is correct
8 Correct 153 ms 20096 KB Output is correct
9 Correct 153 ms 20156 KB Output is correct
10 Correct 147 ms 20052 KB Output is correct
11 Correct 95 ms 19024 KB Output is correct
12 Correct 92 ms 19112 KB Output is correct
13 Correct 86 ms 19056 KB Output is correct
14 Correct 87 ms 19056 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 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 Runtime error 1446 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -