oj.uz

Submission #1032832

# Submission time Handle Problem Language Result Execution time Memory
1032832 2024-07-24T09:29:57 Z amirhoseinfar1385 Highway Tolls (IOI18_highway) C++17
0 / 100
 1500 ms 3928 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=90000+10;
int n,a,b,aval,s,t;
int m,sz[maxn],vis[maxn];
vector<int>adj[maxn];

struct yal{
  int u,v;
  int getad(int fu){
    return (fu^v^u);
  }
}alle[maxn];

int pors(vector<int>er){
  vector<int>ret(m);
  for(auto x:er){
    ret[x]=1;
  }
  return ask(ret);
}

void calsz(int u,int par=-1){
  sz[u]=1;
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(vis[v]==0&&v!=par){
      calsz(v,u);
      sz[u]+=sz[v];
    }
  }
}

int findcen(int u,int szz){
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(vis[v]==0&&sz[v]*2>szz){
      return findcen(v,szz);
    }
  }
  return u;
}

int finds(int u=1){
  calsz(u);
  int v=findcen(u,sz[u]);
  vector<int>tof;
  for(auto x:adj[v]){
    int z=alle[x].getad(v);
    if(vis[z]==0){
      tof.push_back(x);
    }
  }
  int fake=pors(tof);
  if(fake==aval){
    return v;
  }
  int low=-1,high=(int)tof.size(),mid;
  while(high-low>1){
    mid=(high+low)>>1;
    vector<int>ers;
    for(int i=0;i<=mid;i++){
      ers.push_back(tof[i]);
    }
    fake=pors(ers);
    if(fake==aval){
      low=mid;
    }else{
      high=mid;
    }
  }
  vis[v]=1;
  return finds(alle[tof[high]].getad(v));
}
vector<int>ham;
int bal[maxn];

void dfscal(int u,int len,int par=-1,int now=0){
  if(now==len){
    ham.push_back(u);
    return ;
  }
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(v==par){
      continue;
    }
    dfscal(v,len,u,now+1);
  }
}

int findt(){
  dfscal(s,aval/a);
  int low=-1,high=(int)ham.size()-1,mid;
  while(high-low>1){
    vector<int>ers;
    mid=(high+low)>>1;
    for(int i=0;i<=mid;i++){
      ers.push_back(bal[ham[i]]);
    }
    long long fake=pors(ers);
    if(fake==aval){
      low=mid;
    }else{
      high=mid;
    }
  }
  return ham[high];
}

void calc(){
  s=finds();
  t=findt();
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  n=N;
  m = U.size();
  a=A;
  b=B;
 for(int i=0;i<m;i++){
  alle[i].u=U[i];
  alle[i].v=V[i];
  adj[U[i]].push_back(i);
  adj[V[i]].push_back(i);
 }
 if(m!=n-1){
  answer(0,1);
  return ;
 }
 aval=pors({});
 calc();
  answer(s,t);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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