oj.uz

Submission #1032842

# Submission time Handle Problem Language Result Execution time Memory
1032842 2024-07-24T09:37:04 Z amirhoseinfar1385 Highway Tolls (IOI18_highway) C++17
5 / 100
 78 ms 8896 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,int par=-1){
  for(auto x:adj[u]){
    int v=alle[x].getad(u);
    if(vis[v]==0&&sz[v]*2>szz&&v!=par){
      return findcen(v,szz,u);
    }
  }
  return u;
}

int finds(int u=0){
 // cout<<u<<endl;
  calsz(u);
 // cout<<u<<endl;
  int v=findcen(u,sz[u]);
 // cout<<u<<endl;
  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;
    }
    bal[v]=x;
    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(){
 // 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(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();
  //cout<<s<<" "<<t<<endl;
  answer(s,t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 7 ms 4024 KB Output is correct
3 Correct 71 ms 8456 KB Output is correct
4 Correct 67 ms 8396 KB Output is correct
5 Correct 78 ms 8176 KB Output is correct
6 Correct 69 ms 8188 KB Output is correct
7 Correct 63 ms 8368 KB Output is correct
8 Correct 66 ms 8376 KB Output is correct
9 Correct 64 ms 8172 KB Output is correct
10 Correct 64 ms 8456 KB Output is correct
11 Correct 73 ms 8400 KB Output is correct
12 Correct 68 ms 8896 KB Output is correct
13 Correct 61 ms 8884 KB Output is correct
14 Incorrect 59 ms 7984 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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