oj.uz

Submission #1026975

# Submission time Handle Problem Language Result Execution time Memory
1026975 2024-07-18T16:02:41 Z Malix Highway Tolls (IOI18_highway) C++14
51 / 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});
  }

 
  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);
    }
  }

  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){
        if(arr[val[q]]==1)break;
        arr[val[q]]=1;
        q=p[q];
        e--;
      }
    }

    if(ask(arr)>d*A)r=mid;
    else l=mid+1;
  }

  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);
        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];


  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;
  }
  answer(ans1, b[l]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 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 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 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 10 ms 2508 KB Output is correct
3 Correct 110 ms 20072 KB Output is correct
4 Correct 107 ms 20036 KB Output is correct
5 Correct 110 ms 20052 KB Output is correct
6 Correct 107 ms 20212 KB Output is correct
7 Correct 110 ms 20140 KB Output is correct
8 Correct 114 ms 20096 KB Output is correct
9 Correct 103 ms 20140 KB Output is correct
10 Correct 109 ms 20048 KB Output is correct
11 Correct 110 ms 19092 KB Output is correct
12 Correct 116 ms 19108 KB Output is correct
13 Correct 111 ms 19104 KB Output is correct
14 Correct 98 ms 19264 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2136 KB Output is correct
2 Correct 16 ms 4184 KB Output is correct
3 Correct 22 ms 5976 KB Output is correct
4 Correct 72 ms 19024 KB Output is correct
5 Correct 74 ms 19112 KB Output is correct
6 Correct 76 ms 19356 KB Output is correct
7 Correct 72 ms 19024 KB Output is correct
8 Correct 72 ms 19056 KB Output is correct
9 Correct 72 ms 19024 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 12 ms 2392 KB Output is correct
3 Correct 91 ms 15812 KB Output is correct
4 Correct 119 ms 20048 KB Output is correct
5 Correct 101 ms 19980 KB Output is correct
6 Correct 107 ms 20048 KB Output is correct
7 Correct 100 ms 19972 KB Output is correct
8 Correct 128 ms 20388 KB Output is correct
9 Correct 111 ms 19976 KB Output is correct
10 Correct 110 ms 20096 KB Output is correct
11 Correct 111 ms 19108 KB Output is correct
12 Correct 103 ms 19100 KB Output is correct
13 Correct 100 ms 19124 KB Output is correct
14 Correct 115 ms 19104 KB Output is correct
15 Correct 103 ms 20144 KB Output is correct
16 Correct 93 ms 19968 KB Output is correct
17 Correct 98 ms 19104 KB Output is correct
18 Correct 108 ms 19084 KB Output is correct
19 Correct 102 ms 20152 KB Output is correct
20 Correct 101 ms 19104 KB Output is correct
21 Correct 119 ms 21328 KB Output is correct
22 Correct 100 ms 21316 KB Output is correct
23 Correct 103 ms 20608 KB Output is correct
24 Correct 112 ms 20484 KB Output is correct
25 Correct 102 ms 19516 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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