Submission #740402

#	Time	Username	Problem	Language	Result	Execution time	Memory
740402		danikoynov	Highway Tolls (IOI18_highway)	C++14	51 / 100	238 ms	262144 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, 0);
    for (int v : act)
        res[v] = 1;
    return res;
}


int mark[maxn], from[maxn], dis[maxn];

void mark_vertices(int v, int p)
{
    mark[v] = 1;
    for (pair < int, int > nb : g[v])
    {
        if (nb.first == p)
            continue;
            from[nb.first] = nb.second;
        dis[nb.first] = dis[v] + 1;
        mark_vertices(nb.first, v);
    }
}

int used[maxn];
int find_under(int v, int p, ll len)
{
    for (int i = 0; i < n; i ++)
    {
        used[i] = 0;
        mark[i] = 0, from[i] = 0, dis[i] = 0;
    }
    used[p] = 1;
    from[v] = -1;
    mark_vertices(v, p);

    vector < int > act;
    for (int i = 0; i < m; i ++)
    {
        if (mark[ed[i].first] && mark[ed[i].second])
            act.push_back(i);
    }

    ll val = ask(turn_active(act));
    ll nec = (val - len * a) / (ll)(b - a);
    act.clear();
    for (int i = 0; i < n; i ++)
    {
        if (mark[i] && dis[i] == nec)
            act.push_back(from[i]), used[from[i]] = 1;
    }


    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)) != len * a)
                act = lf;
            else
                act = rf;
    }

    int edge = act[0];
    for (int i = 0; i < n; i ++)
    {
        if (mark[i] && dis[i] == nec && from[i] == edge)
            return i;
    }

    return -1 ;

}
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 < n - 1; i ++)
    act.push_back(i);

    ll num_edges = ask(turn_active(act)) / (ll)(B);
    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)(A))
            act = lf;
        else
            act = rf;
    }

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

    int S = find_under(v, u, num_edges);
    int T = find_under(u, v, num_edges);
    ///cout << S << " " << T << " : " << v << " " << u << endl;
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'void mark_vertices(int, int)':
highway.cpp:28:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   28 |         if (nb.first == p)
      |         ^~
highway.cpp:30:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   30 |             from[nb.first] = nb.second;
      |             ^~~~
highway.cpp: In function 'int find_under(int, int, ll)':
highway.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0; i < act.size() / 2; i ++)
      |                         ~~^~~~~~~~~~~~~~~~
highway.cpp:70:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int i = act.size() / 2; i < act.size(); i ++)
      |                                      ~~^~~~~~~~~~~~
highway.cpp:70:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |         for (int i = act.size() / 2; i < act.size(); i ++)
      |         ^~~
highway.cpp:72:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |             if (ask(turn_active(lf)) != len * a)
      |             ^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int i = 0; i < act.size() / 2; i ++)
      |                         ~~^~~~~~~~~~~~~~~~
highway.cpp:113:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         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