Submission #113664

#	Time	Username	Problem	Language	Result	Execution time	Memory
113664		zoooma13	Highway Tolls (IOI18_highway)	C++14	18 / 100	242 ms	24964 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 <int> perm ,ori;

int depth[MAX_N];
vector <int> atdep[MAX_N];
void dfs(int u ,int p ,int d=1){
    depth[u] = d;
    for(auto v : adj[u]) if(v.first != p){
        atdep[d].push_back(v.second);
        dfs(v.first ,u ,d+1);
    }
}

int solve(int u ,int v ,long long dist){
    memset(depth ,0 ,sizeof depth);
    for(int i=0; i<MAX_N; i++)
        atdep[i].clear();

    dfs(u ,v);

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

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

    if(en == -1)
        return u;
    u = edges[eds[en]].first ,v = edges[eds[en]].second;
    return depth[u] > depth[v] ? u : v;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    n = N; assert(U.size() == N-1);

    perm.resize(n-1) ,ori.resize(n-1);
    iota(perm.begin() ,perm.end() ,0);
    shuffle(perm.begin() ,perm.end() ,rng);
    vector <int> u(n-1) ,v(n-1);
    for(int i=0; i<n-1; i++){
        ori[perm[i]] = i;
        u[perm[i]] = U[i] ,v[perm[i]] = V[i];
    }

    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[ori[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)

highway.cpp: In function 'int solve(int, int, long long int)':
highway.cpp:42:35: warning: right operand of comma operator has no effect [-Wunused-value]
     st = 0 ,en = eds.size()-1 ,mid;
                                   ^
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:63:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     n = N; assert(U.size() == N-1);
                   ~~~~~~~~~^~~~~~

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