Submission #1060081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060081		jerzyk	Highway Tolls (IOI18_highway)	C++14	100 / 100	194 ms	65312 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 1000 * 1000 * 1000 * 2;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll bas, A, B;
vector<int>ed[N], num[N];
vector<int> cnd;
int dis[N];
vector<int> cur;

bool vis[N];
vector<int> clr[2];

void DFS(int v, int cur)
{
    clr[cur].pb(v); vis[v] = true;
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if(!vis[ed[v][i]])
            DFS(ed[v][i], cur ^ 1);
}

bool Question(int pos)
{
    for(int i = pos; i < (int)cur.size(); ++i)
    {
        int v = cur[i];
        for(int j = 0; j < (int)num[v].size(); ++j)
            cnd[num[v][j]] = 1;
    }
    ll ans = ask(cnd);
    for(int i = 0; i < (int)cnd.size(); ++i)
        cnd[i] = 0;
    return (ans > bas);
}

int BS()
{
    int p = 0, k = (int)cur.size(), s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Question(s))
            p = s;
        else
            k = s - 1;
    }
    return cur[p];
}

void BFS(int s, int n)
{
    int v; queue<int> q;
    for(int i = 0; i <= n; ++i)
        dis[i] = II;
    dis[s] = 0;
    q.push(s);
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(dis[ed[v][i]] > dis[v] + 1)
            {
                dis[ed[v][i]] = dis[v] + 1;
                q.push(ed[v][i]);
            }
        }
    }
}

void DoCur1(int n)
{
    vector<pair<int, int>> hlp;
    for(int i = 0; i < n; ++i)
        hlp.pb(make_pair(dis[i], i));
    sort(hlp.begin(), hlp.end());
    cur.clear();
    for(int i = 0; i < n; ++i)
        cur.pb(hlp[i].nd);
    /*cerr << "cur1 \n";
    for(int i = 0; i < n; ++i)
        cout << cur[i] << " ";
    cout << "\n";*/
}

void DoCur2(int n, int il)
{
    cur.clear();
    for(int i = 0; i < n; ++i)
        if(dis[i] == il)
            cur.pb(i);
}

void find_pair(int N, vector<int> U, vector<int> V, int XA, int XB)
{
    A = XA; B = XB;
    int n = N;
    for(int i = 0; i < (int)U.size(); ++i)
    {
        ed[U[i]].pb(V[i]); ed[V[i]].pb(U[i]);
        num[U[i]].pb(i); num[V[i]].pb(i);
        cnd.pb(0);
    }
    bas = ask(cnd);
    DFS(0, 0);
    if((int)clr[1].size() >= 1 && clr[1].size() < clr[0].size())
        swap(clr[1], clr[0]);
    cur = clr[0];


    int mid = BS(), s, t;
    //cerr << mid << "\n";
    BFS(mid, n);
    DoCur1(n);
    s = BS();
    //cerr << s << "\n";
    BFS(s, n);
    DoCur2(n, bas / A);
    t = BS();
    answer(s, t);
}

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