Submission #1238932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238932		LeonidCuk	Highway Tolls (IOI18_highway)	C++17	51 / 100	247 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,timer=0;
vector<vector<pair<int,int>>>g;
vector<int>es,en,tour;
void dfs(int a,int b)
{
  es[a]=timer;timer++;
  for(auto i:g[a])
  {
    if(i.first!=b)
    {
      tour.push_back(i.second);
      dfs(i.first,a);
    }
  }
  en[a]=timer-1;
}
bool check(int a,int b)
{
  return es[a]<=es[b]&&en[b]<=en[a];
}
void find_pair(int N,vector<int> U,vector<int> V, int A, int B) {
  n=N;
  m=U.size();
  g.resize(n);
  es.resize(n);
  en.resize(n);
  for(int i=0;i<m;i++)
  {
    g[U[i]].push_back({V[i],i});
    g[V[i]].push_back({U[i],i});
  }
  vector<int>v(m);
  long long sum=ask(v);
  dfs(0,0);
  int l=0,r=m-1;
  while(r>l)
  {
    int mid=(l+r+1)/2;
    for(int i=mid;i<m;i++)v[tour[i]]=1;
    long long temp=ask(v);
    for(int i=mid;i<m;i++)v[tour[i]]=0;
    if(temp!=sum)l=mid;
    else r=mid-1;
  }
  int x,y;
  if(check(U[tour[l]],V[tour[l]]))x=V[tour[l]];
  else x=U[tour[l]];
  while(!tour.empty())tour.pop_back();
  timer=0;
  dfs(x,x);
  l=0;r=m-1;
  while(r>l)
  {
    int mid=(l+r+1)/2;
    for(int i=mid;i<m;i++)v[tour[i]]=1;
    long long temp=ask(v);
    for(int i=mid;i<m;i++)v[tour[i]]=0;
    if(temp!=sum)l=mid;
    else r=mid-1;
  }
  if(check(U[tour[l]],V[tour[l]]))y=V[tour[l]];
  else y=U[tour[l]];
  answer(x,y);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31