Submission #75610

#	Time	Username	Problem	Language	Result	Execution time	Memory
75610		polyfish	통행료 (IOI18_highway)	C++14	12 / 100	486 ms	262148 KiB

highway

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

const int MAX_N = 90002;
const int MAX_M = 130002;

int n, m, A, B, d, edge_id, s, t, ls, lt, depth_x[MAX_N];
bool ok[MAX_N];
vector<pair<int, int> > e, g[MAX_N];
vector<int> W;

void find_distance() {
    d = ask(vector<int>(m)) / A;
}

int solve_equation(int64_t a1, int64_t b1, int64_t c1, int64_t a2, int64_t b2, int64_t c2) {
    int64_t D = a1 * b2 - a2 * b1;
    int64_t Dx = c1 * b2 - c2 * b1;
    return Dx / D;
}

void find_an_arbitrary_edge_on_the_path() {
    int l = 0, r = m-1;
    vector<int> w(m, 0);
    while (l<r) {
        int mid = (l + r) / 2;
        for (int i=0; i<m; ++i)
            w[i] = 1;
        for (int i=l; i<=mid; ++i)
            w[i] = 0;
        int tmp = ask(w);
        if (solve_equation(1, 1, d, A, B, tmp)>0)
            r = mid;
        else
            l = mid+1;
    }
    edge_id = l;
}

void fill_zero(int u, int par) {
    for (int i=0; i<g[u].size(); ++i) {
        int v = g[u][i].first, id = g[u][i].second;
        if (v!=par) {
            W[id] = 0;
            fill_zero(v, u);
        }
    }
}

void find_ls_lt() {
    W.assign(m, 1);
    W[edge_id] = 0;
    fill_zero(e[edge_id].second, e[edge_id].first);
    ls = solve_equation(1, 1, d, A, B, ask(W));
    lt = d - ls;
}

void upd(int u, int par) {
    for (int i=0; i<g[u].size(); ++i) {
        int v = g[u][i].first, id = g[u][i].second;
        if (v!=par) {
            depth_x[v] = depth_x[u] + !W[id];
            upd(v, u);
        }
    }
}

void find_t() {
    memset(ok, true, sizeof(ok));
    while (true) {
        W.clear();
        for (int i=0; i<m; ++i)
            W.push_back(rand()%2);
        W[edge_id] = 0;
        fill_zero(e[edge_id].second, e[edge_id].first);
        int tmp = solve_equation(1, 1, lt, A, B, ask(W) - 1LL * ls * A);
        upd(e[edge_id].first, -1);
        int cnt = 0, pos;
        for (int i=0; i<n; ++i) {
            ok[i] = ok[i] && depth_x[i]==tmp;
            if (ok[i]) {
                ++cnt;
                pos = i;
            }
        }
        if (cnt==1) {
            t = pos;
            break;
        }
    }
}

void find_s() {
    memset(ok, true, sizeof(ok));
    while (true) {
        W.clear();
        for (int i=0; i<m; ++i)
            W.push_back(rand()%2);
        int tmp = solve_equation(1, 1, d, A, B, ask(W));
        depth_x[t] = 0;
        upd(t, -1);
        int cnt = 0, pos;
        for (int i=0; i<n; ++i) {
            ok[i] = ok[i] && (depth_x[i] == tmp);
            if (ok[i]) {
                ++cnt;
                pos = i;
            }
        }
        if (cnt==1) {
            s = pos;
            break;
        }
    }
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int _A, int _B) {
    srand(time(NULL));
    n = N;
    m = U.size();
    A = _A;
    B = _B;
    for (int i=0; i<m; ++i) {
        e.push_back(make_pair(U[i], V[i]));
        g[U[i]].push_back(make_pair(V[i], i));
        g[V[i]].push_back(make_pair(U[i], i));
    }
    find_distance();
    find_an_arbitrary_edge_on_the_path();
    find_ls_lt();
    find_t();
    find_s();
    answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'void fill_zero(int, int)':
highway.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<g[u].size(); ++i) {
                   ~^~~~~~~~~~~~
highway.cpp: In function 'void upd(int, int)':
highway.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<g[u].size(); ++i) {
                   ~^~~~~~~~~~~~
highway.cpp: In function 'void find_t()':
highway.cpp:88:15: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
             t = pos;
             ~~^~~~~
highway.cpp: In function 'void find_s()':
highway.cpp:112:15: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
             s = pos;
             ~~^~~~~

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