Submission #157045

#	Time	Username	Problem	Language	Result	Execution time	Memory
157045		Alexa2001	Highway Tolls (IOI18_highway)	C++17	90 / 100	610 ms	19680 KiB

highway

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

using namespace std;

typedef long long ll;

const int Nmax = 150005;

vector<int> w, nodes;
vector<int> down[Nmax];
vector<pair<int,int>> edge[Nmax];

int n, m;



void dfs(int node)
{
    nodes.push_back(node);
    for(auto it : down[node])
        dfs(it);
}

int solve(int id, int root, ll cost, vector<int> &u, vector<int> &v)
{
    int i;
    for(i=0; i<n; ++i) edge[i].clear();
    for(i=0; i<n; ++i) down[i].clear();
    nodes.clear();

    for(i=0; i<=id; ++i)
    {
        edge[u[i]].push_back({ v[i], i });
        edge[v[i]].push_back({ u[i], i });
    }

    queue<int> q;
    q.push(root);

    vector<int> parent(n, -1);
    vector<int> dist(n, 1e9);

    parent[root] = root;
    dist[root] = 0;

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : edge[node])
            if(parent[it.first] == -1)
            {
                dist[it.first] = dist[node] + 1;
                parent[it.first] = node;
                q.push(it.first);
                down[node].push_back(it.first);
            }
    }

    dfs(root);

    int st, dr, mid;
    st = 0; dr = nodes.size() - 1;

    while(st <= dr)
    {
        mid = (st + dr) / 2;

        for(i=0; i<=id; ++i) w[i] = 0;
        for(; i<m; ++i) w[i] = 1;

        for(i=mid+1; i<nodes.size(); ++i)
            for(auto it : edge[nodes[i]])
                if(dist[it.first] < dist[nodes[i]])
                    w[it.second] = 1;

        if(cost == ask(w)) dr = mid - 1;
            else st = mid + 1;
    }
    assert(st < nodes.size() && st >= 0);
    return nodes[st];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    n = N;
    m = U.size();
    w.resize(m, 0);

    int st, dr, mid;
    int i;

    ll initial_cost = ask(w);

    st = 1; dr = m;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        for(i=0; i<mid; ++i) w[i] = 0;
        for(; i<m; ++i) w[i] = 1;

        if(ask(w) == initial_cost) dr = mid - 1;
            else st = mid + 1;
    }

    /// indicele dr e special

    int X, Y;

    X = solve(dr, V[dr], initial_cost, U, V);
    Y = solve(dr, X, initial_cost, U, V);

    answer(X, Y);
}

Compilation message (stderr)

highway.cpp: In function 'int solve(int, int, ll, std::vector<int>&, std::vector<int>&)':
highway.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mid+1; i<nodes.size(); ++i)
                      ~^~~~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from highway.cpp:2:
highway.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(st < nodes.size() && st >= 0);
            ~~~^~~~~~~~~~~~~~

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