제출 #1232630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232630		Hanksburger	통행료 (IOI18_highway)	C++17	100 / 100	721 ms	29000 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<pair<ll, ll>, ll> mp;
vector<ll> adj[90005];
ll dist[2][90005], t;
bool cmp(ll x, ll y)
{
    return dist[t][x]<dist[t][y];
}
void find_pair(int n, vector<int> uu, vector<int> vv, int a, int b)
{
    ll m=uu.size();
    for (ll i=0; i<m; i++)
    {
        adj[uu[i]].push_back(vv[i]);
        adj[vv[i]].push_back(uu[i]);
        mp[{uu[i], vv[i]}]=mp[{vv[i], uu[i]}]=i;
    }
    vector<int> tmp(m, 0);
    ll res=ask(tmp), l=0, r=m-1;
    while (l<r)
    {
        ll mid=(l+r)/2;
        for (ll i=0; i<=mid; i++)
            tmp[i]=1;
        for (ll i=mid+1; i<m; i++)
            tmp[i]=0;
        if (ask(tmp)==res)
            l=mid+1;
        else
            r=mid;
    }
    ll node[2]={uu[l], vv[l]};
    for (ll i=0; i<2; i++)
    {
        queue<ll> q;
        for (ll j=0; j<n; j++)
            dist[i][j]=1e9;
        dist[i][node[i]]=0;
        q.push(node[i]);
        while (!q.empty())
        {
            ll u=q.front();
            q.pop();
            for (ll v:adj[u])
            {
                if (dist[i][u]+1<dist[i][v])
                {
                    dist[i][v]=dist[i][u]+1;
                    q.push(v);
                }
            }
        }
    }
    ll ans[2];
    for (t=0; t<2; t++)
    {
        vector<ll> vec;
        for (ll i=0; i<n; i++)
            if (dist[t][i]<dist[t^1][i])
                vec.push_back(i);
        sort(vec.begin(), vec.end(), cmp);
        ll L=0, R=vec.size()-1;
        while (L<R)
        {
            ll mid=(L+R+1)/2;
            vector<int> tmp2(m, 0);
            for (ll i=0; i<m; i++)
            {
                if (i==l)
                    continue;
                ll type1=(dist[t][uu[i]]<dist[t^1][uu[i]]?1:(dist[t][uu[i]]>dist[t^1][uu[i]]?3:2));
                ll type2=(dist[t][vv[i]]<dist[t^1][vv[i]]?1:(dist[t][vv[i]]>dist[t^1][vv[i]]?3:2));
                if (type1==2 || type2==2 || type1!=type2)
                    tmp2[i]=1;
            }
            for (ll i=mid; i<vec.size(); i++)
                for (ll j:adj[vec[i]])
                    if (dist[t][j]<dist[t][vec[i]])
                        tmp2[mp[{vec[i], j}]]=1;
            if (ask(tmp2)==res)
                R=mid-1;
            else
                L=mid;
        }
        ans[t]=vec[L];
    }
    answer(ans[0], ans[1]);
}

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