Submission #147192

#	Time	Username	Problem	Language	Result	Execution time	Memory
147192		Bodo171	Highway Tolls (IOI18_highway)	C++14	69 / 100	391 ms	12576 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax=100005;
const int mmax=130005;
int n,m,i,p,u,ret;
long long mx,cate,A,B;
int unu[mmax],doi[mmax];
bool always[mmax];
bool inA[nmax],inB[nmax];
int in[nmax],bun[nmax];
int qu[2][nmax],d[2][nmax];
vector<int> v[nmax];
vector<int> q;
long long dist(int x)
{
    for(i=0;i<m;i++)
        q[i]=1;
    for(i=0;i<x;i++)
        q[i]=0;
    return ask(q);
}
void bfs(int x,int wh)
{
    int nod;
    u=1;
    qu[wh][u]=x;d[wh][x]=1;
    for(p=1;p<=u;p++)
    {
        x=qu[wh][p];
        for(i=0;i<v[x].size();i++)
        {
            nod=v[x][i];
            if(!d[wh][nod])
            {
                d[wh][nod]=d[wh][x]+1;
                qu[wh][++u]=nod;
            }
        }
    }
}
int cb(vector<int> mult)
{
    int ans=0;
    for(i=0;i<n;i++)
        in[i]=0;
    for(i=0;i<mult.size();i++)
        in[mult[i]]=1;
    for(int p=17;p>=0;p--)
        if(ans+(1<<p)<=mult.size())
    {
        ans+=(1<<p);
        for(i=0;i<m;i++)
          if(always[i]) q[i]=0;
          else q[i]=1;
        q[ret]=0;
        for(i=0;i<n;i++)
            bun[i]=0;
        for(i=0;i<ans;i++)
            bun[mult[i]]=1;
        for(i=0;i<m;i++)
            if(bun[unu[i]]&&bun[doi[i]])
               q[i]=0;
        long long cat=ask(q);
        if(cat==1LL*cate*A) ans-=(1<<p);
    }
    return mult[ans];
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int Aa, int Bb) {
  n=N;m = U.size();
  q.resize(m);
  A=Aa;B=Bb;
  for(i=0;i<m;i++)
  {
      v[U[i]].push_back(V[i]);
      v[V[i]].push_back(U[i]);
      unu[i]=U[i];doi[i]=V[i];
  }
  for(i=0;i<m;i++)
    q[i]=1;
  mx=ask(q);
  cate=mx/B;
  for(int p=17;p>=0;p--)
     if(ret+(1<<p)<=m&&dist(ret+(1<<p))==mx)
        ret+=(1<<p);
   int a=U[ret],b=V[ret];
   bfs(a,0);bfs(b,1);
   vector<int> multA,multB;
   for(i=1;i<=n;i++)
   {
        int nod=qu[0][i];
        if(d[0][nod]<d[1][nod])
        {
            multA.push_back(nod);
            inA[nod]=1;
        }
        nod=qu[1][i];
        if(d[1][nod]<d[0][nod])
        {
            multB.push_back(nod);
            inB[nod]=1;
        }
   }
   for(i=0;i<m;i++)
    if(inB[U[i]]&&inB[V[i]])
       always[i]=1;
   int x=cb(multA);
   for(i=0;i<m;i++)
    always[i]=0;
   for(i=0;i<m;i++)
     if(inA[U[i]]&&inA[V[i]])
       always[i]=1;
   int y=cb(multB);
   answer(x,y);
}

Compilation message (stderr)

highway.cpp: In function 'void bfs(int, int)':
highway.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
highway.cpp: In function 'int cb(std::vector<int>)':
highway.cpp:47:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<mult.size();i++)
             ~^~~~~~~~~~~~
highway.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ans+(1<<p)<=mult.size())
            ~~~~~~~~~~^~~~~~~~~~~~~

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