Submission #1082152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082152		TlenekWodoru	Highway Tolls (IOI18_highway)	C++17	51 / 100	133 ms	9788 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
struct Edge
{
    int b,c;
};
vector<Edge>D[90009];
int n,m;
vector<int>E1,E2;
long long DeafOdl;
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;
        vector<int>Query(m);
        for(int i=0;i<mid;i++)
        {
            for(auto[som,ind] : D[i])
            {
                Query[ind]=1;
            }
        }
        if(ask(Query)!=DeafOdl)
        {
            p=mid;
        }
        else
        {
            l=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(m);
        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>EE1, vector<int>EE2, int A, int B)
{
    n=N;
    m=EE1.size();
    E1=EE1;
    E2=EE2;
    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();
    int a=BinSearch2(u);
    int b=BinSearch2(a);
    if(a>b){swap(a,b);}
    answer(a,b);
}

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