Submission #743528

#	Time	Username	Problem	Language	Result	Execution time	Memory
743528		danikoynov	Highway Tolls (IOI18_highway)	C++14	51 / 100	229 ms	16712 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
vector < pair < int, int > > g[maxn];
int n, m;
ll a, b;
pair < int, int > ed[maxn];

vector < int > turn_active(vector < int > act)
{
    vector < int > res(m, 1);
    for (int v : act)
        res[v] = 0;
    return res;
}
vector < int > turn_inactive(vector < int > act)
{
    vector < int > res(m, 0);
    for (int v : act)
        res[v] = 1;
    return res;
}
int mark[maxn], from[maxn], dis[maxn];
int used[maxn];
int sub_solve(int s, vector < int > st, ll sum)
{
    for (int i = 0; i < n; i ++)
        used[i] = 1e9;
    for (int v : st)
        used[v] = -1;
    used[s] = 0;
    queue < int > q;
    q.push(s);
    from[s] = -1;
    vector < int > d;
    vector < int > base;
    ///exit(0);
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        d.push_back(v);
        for (pair < int, int > nb : g[v])
        {
            if (used[nb.first] == -1)
            {
                used[nb.first] = used[v] + 1;
                from[nb.first] = nb.second;
                base.push_back(nb.second);
                q.push(nb.first);
            }
        }
    }

    int lf = 1, rf = (int)(d.size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        vector < int > cur_set;
        for (int i = max(1,mf); i < d.size(); i ++)
            cur_set.push_back(from[d[i]]);
        if (ask(turn_inactive(cur_set)) != sum)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    return d[rf];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    n = N;
    m = U.size();
    a = A;
    b = B;
    for (int i = 0; i < m; i ++)
    {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
        ed[i] = {U[i], V[i]};
    }


    vector < int > act;
    for (int i = 0; i < m; i ++)
    act.push_back(i);

    ll base_sum = ask(turn_active(act));
    ll num_edges = base_sum / (ll)(A);
    while(act.size() > 1)
    {
        vector < int > lf, rf;
        for (int i = 0; i < act.size() / 2; i ++)
            lf.push_back(act[i]);
        for (int i = act.size() / 2; i < act.size(); i ++)
            rf.push_back(act[i]);

        if (ask(turn_active(lf)) != num_edges * (ll)(B))
            act = lf;
        else
            act = rf;
    }

    int edge = act[0];
    ///cout << "here " << edge << endl;
    int v = V[edge], u = U[edge];

    queue < int > q;
    mark[v] = 1;
    mark[u] = 2;
    q.push(v);
    q.push(u);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        ///cout << cur << " : " << mark[cur] << endl;
        for (pair < int, int > nb : g[cur])
        {
            if (mark[nb.first] == 0)
            {
                mark[nb.first] = mark[cur];
                q.push(nb.first);
            }
        }
    }
    vector < int > set_s, set_t;
    for (int i = 0; i < n; i ++)
    {
        if (mark[i] == 1)
            set_s.push_back(i);
        else
            set_t.push_back(i);
    }
    int S = sub_solve(v, set_s, base_sum), T = sub_solve(u, set_t, base_sum);
    ///cout << S << " " << T << " : " << v << " " << u << endl;
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'int sub_solve(int, std::vector<int>, ll)':
highway.cpp:63:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = max(1,mf); i < d.size(); i ++)
      |                                 ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for (int i = 0; i < act.size() / 2; i ++)
      |                         ~~^~~~~~~~~~~~~~~~
highway.cpp:98:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i = act.size() / 2; i < act.size(); i ++)
      |                                      ~~^~~~~~~~~~~~

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