oj.uz

Submission #75610

# Submission time Handle Problem Language Result Execution time Memory
75610 2018-09-10T13:53:53 Z polyfish Highway Tolls (IOI18_highway) C++14
12 / 100
 486 ms 262148 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);
    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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2448 KB Output is correct
3 Correct 4 ms 2448 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2472 KB Output is correct
6 Correct 4 ms 2472 KB Output is correct
7 Correct 4 ms 2572 KB Output is correct
8 Correct 5 ms 2424 KB Output is correct
9 Correct 4 ms 2444 KB Output is correct
10 Correct 4 ms 2528 KB Output is correct
11 Correct 3 ms 2424 KB Output is correct
12 Correct 5 ms 2472 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 32 ms 3192 KB Output is correct
3 Correct 311 ms 8744 KB Output is correct
4 Correct 301 ms 8740 KB Output is correct
5 Correct 338 ms 8852 KB Output is correct
6 Correct 265 ms 8724 KB Output is correct
7 Correct 328 ms 8840 KB Output is correct
8 Correct 348 ms 8796 KB Output is correct
9 Correct 327 ms 8732 KB Output is correct
10 Correct 288 ms 8736 KB Output is correct
11 Correct 268 ms 8980 KB Output is correct
12 Correct 308 ms 9664 KB Output is correct
13 Correct 284 ms 9248 KB Output is correct
14 Correct 241 ms 9244 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3532 KB Output is correct
2 Correct 43 ms 4540 KB Output is correct
3 Correct 62 ms 5620 KB Output is correct
4 Correct 174 ms 10688 KB Output is correct
5 Correct 165 ms 10852 KB Output is correct
6 Correct 204 ms 11648 KB Output is correct
7 Correct 167 ms 12160 KB Output is correct
8 Correct 169 ms 11160 KB Output is correct
9 Incorrect 486 ms 12540 KB Output is incorrect: more than 100 calls to ask.

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2472 KB Output is correct
2 Correct 33 ms 3152 KB Output is correct
3 Correct 192 ms 7372 KB Output is correct
4 Correct 268 ms 8776 KB Output is correct
5 Correct 275 ms 8716 KB Output is correct
6 Correct 247 ms 8724 KB Output is correct
7 Correct 326 ms 8828 KB Output is correct
8 Correct 254 ms 8724 KB Output is correct
9 Incorrect 316 ms 8732 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 397 ms 262148 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 366 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -