oj.uz

Submission #1032845

# Submission time Handle Problem Language Result Execution time Memory
1032845 2024-07-24T09:40:23 Z amirhoseinfar1385 Highway Tolls (IOI18_highway) C++17
12 / 100
 80 ms 10260 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;
}

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;
  for(auto x:adj[v]){
    long long z=alle[x].getad(v);
    if(vis[z]==0){
      tof.push_back(x);
    }
  }
  long long fake=pors(tof);
  if(fake==aval){
    return v;
  }
  long long low=-1,high=(long long)tof.size(),mid;
  while(high-low>1){
    mid=(high+low)>>1;
    vector<long long>ers;
    for(long long 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<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
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 6 ms 5136 KB Output is correct
3 Correct 62 ms 10192 KB Output is correct
4 Correct 62 ms 10040 KB Output is correct
5 Correct 66 ms 10024 KB Output is correct
6 Correct 73 ms 9936 KB Output is correct
7 Correct 62 ms 9960 KB Output is correct
8 Correct 64 ms 9968 KB Output is correct
9 Correct 60 ms 9712 KB Output is correct
10 Correct 80 ms 10184 KB Output is correct
11 Correct 66 ms 9492 KB Output is correct
12 Correct 60 ms 9964 KB Output is correct
13 Correct 56 ms 9968 KB Output is correct
14 Correct 65 ms 10260 KB Output is correct

Subtask #3
0 / 6.0

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