Submission #605667

#	Time	Username	Problem	Language	Result	Execution time	Memory
605667		PiejanVDC	Highway Tolls (IOI18_highway)	C++17	0 / 100	246 ms	262144 KiB

highway

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

const int mxN = (int)2e5+5;

long long normal;
vector<int>adj[mxN];

vector<int>x,y;

void answer(int s, int t);
long long ask(const std::vector<int> &w);

void color(int u, int c, int e = -1) {
    if(c) x.push_back(u);
    else y.push_back(u);
    for(auto z : adj[u]) if(z != e) {
        color(z, 1-c, u);
    }
}

int mxDist;
vector<int>p[mxN];
vector<int>re(mxN);

map<pair<int,int>,int>id;

void dfs(int node, int dist, int e = -1) {
    mxDist = max(mxDist, dist);
    if(e > -1) p[dist].push_back(id[{node, e}]);
    re[node] = dist;
    for(auto z : adj[node]) if(z != e) dfs(z, dist+1, node);
}

int M_;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int search_point(vector<int>points) {
    int n = (int)points.size();
    int ans = -1;
    int l = 0, r = n-1;
    while(l <= r) {
        int mid = (l+r)/2;
        vector<int>Ask(M_, 0);
        for(int i = l ; i <= mid ; i++)
            Ask[points[i]] = 1;
        long long R = ask(Ask);
        if(R != normal) {
            r = mid-1;
            ans = mid;
        } else l = mid+1;
    }
    return (ans == -1 ? ans : points[ans]);
}

void find_pair(int n, vector<int>u, vector<int>v, int a, int b) {
    const int m = (int)u.size();
    M_ = m;
    vector<int>dummy(m, 0);
    normal = ask(dummy);

    for(int i = 0 ; i < n-1 ; i++)
        id[{u[i], v[i]}] = id[{v[i], u[i]}] = i, adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);

    color(0, 0);

    int len = normal / a;

    vector<int>w = x;

    while((int)w.size() > 1) {
        //shuffle(w.begin(), w.end(), rng);
        if(w.size() == 2) {
            vector<int>Ask(m, 0);
            for(auto z : adj[w[0]])
                Ask[id[{w[0], z}]] = 1;
            if(((ask(Ask) - normal) / (b - a)) & 1)
                break;
            swap(w[0], w[1]);
            vector<int>Ask2(m, 0);
            for(auto z : adj[w[0]])
                Ask2[id[{w[0], z}]] = 1;
            if(((ask(Ask2) - normal) / (b - a)) & 1)
                break;
            w = y; 
            continue;
        }
        int mid = (int)w.size()/2;
        vector<int>Ask(m, 0);
        for(int i = 0 ; i < mid ; i++) {
            for(auto z : adj[w[i]])
                Ask[id[{w[i], z}]] = 1;
        }
        if(((ask(Ask) - normal) / (b - a)) & 1) {
            while(w.size() > mid)
                w.pop_back();
        }
    }

    int node = w[0];
    dfs(node, 0);

    int R = search_point(p[len]);
    int P = (re[u[R]] > re[v[R]] ? u[R] : v[R]);
    answer(node, P);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:96:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |             while(w.size() > mid)
      |                   ~~~~~~~~~^~~~~

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