Submission #606486

#	Time	Username	Problem	Language	Result	Execution time	Memory
606486		PiejanVDC	Highway Tolls (IOI18_highway)	C++17	51 / 100	608 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;

    int T = 10;
    bool ok = 0;
    while(T--) {
        shuffle(w.begin(), w.end(), rng);
        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();
            ok = 1;
            break;
        }
    }
    if(!ok) {
        w = y;
        while(1) {
            shuffle(w.begin(), w.end(), rng);
            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();
                break;
            }
        }
    }
    while(w.size() > 1) {
        int mid = 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();
        } else {
            vector<int>tmp;
            for(int i = mid ; i < w.size() ; i++)
                tmp.push_back(w[i]);
            swap(w, tmp);  
        }
    }

    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:81:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |             while(w.size() > mid)
      |                   ~~~~~~~~~^~~~~
highway.cpp:96:32: 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)
      |                       ~~~~~~~~~^~~~~
highway.cpp:109:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |             while(w.size() > mid)
      |                   ~~~~~~~~~^~~~~
highway.cpp:113:33: 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 = mid ; i < w.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