제출 #1082186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082186		TlenekWodoru	통행료 (IOI18_highway)	C++17	90 / 100	186 ms	11628 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
struct Edge
{
    int b,c;
};
vector<Edge>D[90009];
int n,m;
long long DeafOdl;
vector<int>DeafQuery;
vector<int>BFS(int s)
{
    vector<int>ODL(n,-1);
    ODL[s]=0;
    deque<int>Y={s};
    vector<int>W;
    while((int)Y.size()>0)
    {
        const int v=Y[0];
        Y.pop_front();
        W.push_back(v);
        for(auto[som,ind] : D[v])
        {
            if(ODL[som]==-1)
            {
                ODL[som]=ODL[v]+1;
                Y.push_back(som);
            }
        }
    }
    return W;
}
int BinSearch()
{
    int l=0,p=n-1;
    while(l<p)
    {
        const int mid=(l+p+1)>>1;
        vector<int>Query(m);
        for(int i=mid;i<n;i++)
        {
            for(auto[som,ind] : D[i])
            {
                Query[ind]=1;
            }
        }
        if(ask(Query)!=DeafOdl)
        {
            l=mid;
        }
        else
        {
            p=mid-1;
        }
    }
    return l;
}
int BinSearch2(int s)
{
    vector<int>W=BFS(s);
    int l=0,p=n-1;
    while(l<p)
    {
        const int mid=(l+p+1)>>1;
        vector<int>Query=DeafQuery;
        for(int i=mid;i<n;i++)
        {
            for(auto[som,ind] : D[W[i]])
            {
                Query[ind]=1;
            }
        }
        if(ask(Query)!=DeafOdl)
        {
            l=mid;
        }
        else
        {
            p=mid-1;
        }
    }
    return W[l];
}
void find_pair(int N, vector<int>E1, vector<int>E2, int A, int B)
{
    n=N;
    m=E1.size();
    for(int i=0;i<m;i++)
    {
        D[E1[i]].push_back({E2[i],i});
        D[E2[i]].push_back({E1[i],i});
    }
    DeafOdl=ask(vector<int>(m));
    int u=BinSearch();
    DeafQuery.resize(m);
    for(int i=u+1;i<n;i++)
    {
        for(auto[som,ind] : D[i])
        {
            DeafQuery[ind]=1;
        }
    }
    int a=BinSearch2(u);
    int b=BinSearch2(a);
    if(a>b){swap(a,b);}
    //cout<<"a="<<a<<" b="<<b<<" u="<<u<<" DeafOdl="<<DeafOdl<<endl;
    answer(a,b);
}

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