oj.uz

Submission #75607

# Submission time Handle Problem Language Result Execution time Memory
75607 2018-09-10T13:40:32 Z polyfish Highway Tolls (IOI18_highway) C++14
0 / 100
 416 ms 262144 KB 
#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);
    fill_zero(e[edge_id].second, e[edge_id].first);
    lt = solve_equation(1, 1, d, A, B, ask(W));
    ls = d - lt;
}

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

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:59: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:87:15: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
             t = pos;
             ~~^~~~~
highway.cpp: In function 'void find_s()':
highway.cpp:111:15: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
             s = pos;
             ~~^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2424 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2584 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3540 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2500 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 416 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 368 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -