Submission #113698

#	Time	Username	Problem	Language	Result	Execution time	Memory
113698		zoooma13	Highway Tolls (IOI18_highway)	C++14	51 / 100	251 ms	10628 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;

#define MAX_N 90004

int n;
vector <pair <int ,int>> adj[MAX_N];
vector <pair <int ,int>> edges;

vector <pair<int ,int>> nodes;
void bfs(int s ,int p){
    nodes.clear();
    vector <int> vis(n ,0);
    vis[s] = vis[p] = 1;

    queue <pair<int,int>> nxt;
    for(auto e : adj[s])
        if(e.first == p)
            nxt.push(e);

    while(!nxt.empty()){
        int u = nxt.front().first ,f = nxt.front().second; nxt.pop();
        nodes.push_back({u,f});
        for(auto e : adj[u])
            if(!vis[e.first])
                nxt.push(e) ,vis[e.first] = 1;
    }
}

int solve(int u ,int v ,long long dist){
    bfs(u ,v);
    int st = 0 ,en = nodes.size()-1 ,mid;
    while(st < en){
        mid = (st+en+1)>>1;
        vector <int> w(n-1 ,0);
        for(int i=mid; i<=en; i++)
            w[nodes[i].second] = 1;
        if(ask(w) != dist)
            st = mid;
        else
            en = mid-1;
    }
    return nodes[st].first;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    n = N;
    assert(U.size() == N-1);
    for(int i=0; i<N-1; i++)
        adj[U[i]].push_back({V[i] ,i}),
        adj[V[i]].push_back({U[i] ,i}),
        edges.push_back({U[i] ,V[i]});

    long long dist = ask(vector<int>(n-1 ,0));
    int st = 0 ,en = n-1 ,mid;
    while(st < en){
        mid = (st+en)>>1;
        vector <int> w(n-1 ,0);
        for(int i=st; i<=mid; i++)
            w[i] = 1;
        if(ask(w) != dist)
            en = mid;
        else
            st = mid+1;
    }

    int s = solve(U[en] ,V[en] ,dist);
    int t = solve(V[en] ,U[en] ,dist);
    answer(s ,t);
}

Compilation message (stderr)

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: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(U.size() == N-1);
            ~~~~~~~~~^~~~~~

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