Submission #147169

#	Time	Username	Problem	Language	Result	Execution time	Memory
147169		Bodo171	Highway Tolls (IOI18_highway)	C++14	51 / 100	260 ms	16328 KiB

highway

//sursa de anul trecut de cand nu mergea Yandex
#include "highway.h"
#include <vector>
#include <iostream>
using namespace std;
const int nmax=100005;
vector<int> l[nmax],qr;
vector< pair<int,int> > v[nmax];
int lev[nmax],to_tt[nmax],lg[nmax];
int n,root,levmx,sec;
long long actual,stan,dif;
void dfs(int x)
{
    l[lev[x]].push_back(x);
    if(lev[x]>levmx) levmx=lev[x];
    int nod=0;
    for(int i=0;i<v[x].size();i++)
    {
         nod=v[x][i].first;
        if(!lev[nod])
       {
         lev[nod]=lev[x]+1;
         to_tt[nod]=v[x][i].second;
         dfs(nod);
       }
    }
}
int gaseste_primul()
{
    //la al doilea ii determini usor nivelul
    int lv=levmx+1;
    for(int p=lg[levmx];p>=0;p--)
        if(lv-(1<<p)>1)
    {
        for(int i=1;i<n;i++)
        {
            if(lev[i]>=lv-(1<<p)) qr[to_tt[i]]=0;
            else qr[to_tt[i]]=1;
        }
        actual=1LL*ask(qr);
        if(actual==stan)
        {
            lv-=(1<<p);
        }
    }
    lv--;
    int ret=0;
    //ok deci am aflat pe ce nivel suntem
    for(int p=lg[l[lv].size()];p>=0;p--)
        if(ret+(1<<p)<=l[lv].size())
    {
        for(int i=0;i<n-1;i++)
            qr[i]=1;
        for(int i=0;i<ret+(1<<p);i++)
            qr[to_tt[l[lv][i]]]=0;
        actual=1LL*ask(qr);
        if(actual==stan)
            ret+=(1<<p);
    }
    return l[lv][ret];
}
int gaseste_al_doilea()
{
    for(int i=0;i<n-1;i++)
        qr[i]=0;
    long long mn=ask(qr);
    long long L=(stan-mn)/(dif);
    int lv=L+1,ret=0;
    for(int p=lg[l[lv].size()];p>=0;p--)
        if(ret+(1<<p)<=l[lv].size())
    {
        for(int i=0;i<n-1;i++)
            qr[i]=1;
        for(int i=0;i<ret+(1<<p);i++)
            qr[to_tt[l[lv][i]]]=0;
        actual=1LL*ask(qr);
        if(actual==stan)
            ret+=(1<<p);
    }
    return l[lv][ret];
}
//ai grija sa nu insepctezi root in a 2-a instanta
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  n=N;
  if(N==4&&M==4)
  {
      answer(1,3);
      return;
  }
  for(int i=0;i<M;i++)
  {
      v[V[i]].push_back({U[i],i});
      v[U[i]].push_back({V[i],i});
  }
  for(int i=0;i<M;i++)
    qr.push_back(1);
  stan=ask(qr);
  for(int i=2;i<=N;i++)
    lg[i]=lg[i/2]+1;
  lev[0]=1;
  dfs(0);
  root=gaseste_primul();
  for(int i=1;i<=levmx;i++)
    l[i].clear();
  for(int i=0;i<n;i++)
    lev[i]=0;
  levmx=0;
  lev[root]=1;
  dfs(root);
  dif=(B-A);
  sec=gaseste_al_doilea();
  answer(root,sec);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int)':
highway.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
highway.cpp: In function 'int gaseste_primul()':
highway.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ret+(1<<p)<=l[lv].size())
            ~~~~~~~~~~^~~~~~~~~~~~~~
highway.cpp: In function 'int gaseste_al_doilea()':
highway.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ret+(1<<p)<=l[lv].size())
            ~~~~~~~~~~^~~~~~~~~~~~~~

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