oj.uz

Submission #1032849

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

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

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

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

long long findcen(long long u,long long szz,long long par=-1){
  for(auto x:adj[u]){
    long long v=alle[x].getad(u);
    if(vis[v]==0&&sz[v]*2>szz&&v!=par){
      return findcen(v,szz,u);
    }
  }
  return u;
}
vector<long long>ersa;

void go(int u,int par=-1){
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(v==par||vis[v]){
      continue;
    }
    ersa.push_back(x);
    go(v,u);
  }
}

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

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

long long findt(){
  dfscal(s,aval/a);
  long long low=-1,high=(long long)ham.size()-1,mid;
  while(high-low>1){
    vector<long long>ers;
    mid=(high+low)>>1;
    for(long long 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(){
 // cout<<"av"<<endl;
  s=finds();
  //s=0;
 // cout<<"dov"<<endl;
  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(long long 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();
  //cout<<s<<" "<<t<<endl;
  answer(s,t);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 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 1 ms 4440 KB Output is correct
2 Correct 9 ms 5392 KB Output is correct
3 Incorrect 107 ms 11952 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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