제출 #147182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147182		Bodo171	통행료 (IOI18_highway)	C++14	0 / 100	30 ms	3660 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];
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(in[unu[i]]==0&&in[doi[i]]==0) 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;
  int ret=0;
  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);
        nod=qu[1][i];
        if(d[1][nod]<d[0][nod]) multB.push_back(nod);
   }
   int x=cb(multA),y=cb(multB);
   answer(x,y);
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void bfs(int, int)':
highway.cpp:29: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:45:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<mult.size();i++)
             ~^~~~~~~~~~~~
highway.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ans+(1<<p)<=mult.size())
            ~~~~~~~~~~^~~~~~~~~~~~~

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