제출 #1082221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1082221		TlenekWodoru	통행료 (IOI18_highway)	C++17	100 / 100	153 ms	12896 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>EE1,EE2;
int O1[90009],O2[90009];
vector<int>BFS(int s, int *O)
{
    memset(O,-1,sizeof(O1));
    O[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(O[som]==-1)
            {
                O[som]=O[v]+1;
                Y.push_back(som);
            }
        }
    }
    return W;
}
int BinSearch()
{
    int l=0,p=m-1;
    while(l<p)
    {
        const int mid=(l+p+1)>>1;
        vector<int>Query(m);
        for(int i=mid;i<m;i++)
        {
            Query[i]=1;
        }
        if(ask(Query)!=DeafOdl)
        {
            l=mid;
        }
        else
        {
            p=mid-1;
        }
    }
    return l;
}
int BinSearch2(int s, vector<int>W)
{
    int l=0,p=W.size()-1;
    while(l<p)
    {
        const int mid=(l+p+1)>>1;
        vector<int>Query(m);
        for(int i=mid;i<(int)W.size();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 uA, int uB)
{
    n=N;
    m=E1.size();
    EE1=E1;
    EE2=E2;
    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 aa=EE1[u],bb=EE2[u];
    vector<int>AA=BFS(aa,O1);
    vector<int>BB=BFS(bb,O2);
    vector<int>A,B;
    for(int u : AA)
    {
        if(O1[u]+1==O2[u]){A.push_back(u);}
    }
    for(int u : BB)
    {
        if(O2[u]+1==O1[u]){B.push_back(u);}
    }
    int a=BinSearch2(aa,A);
    int b=BinSearch2(bb,B);
    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: 31 / 31