oj.uz

Submission #1016954

# Submission time Handle Problem Language Result Execution time Memory
1016954 2024-07-08T16:09:51 Z vyshniak_n Highway Tolls (IOI18_highway) C++17
5 / 100
 84 ms 17140 KB 
//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")

#include "highway.h"
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
using namespace std;
 
#include <random>
mt19937 rnd(time(0));

const int maxn = 9e4 + 10;
vector <pair <int, int>> gr[maxn];
int from[maxn], dist[maxn];

void find_pair(int n, vector <int> u, vector <int> v, int a, int b) {
    int m = u.size();

    vector <int> q(m);
    int len = ask(q) / a;

    int l = -1, r = m;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;

        for (int i = 0; i <= mid; i++)
            q[i] = 1;
        for (int i = mid + 1; i < m; i++)
            q[i] = 0;

        if (ask(q) == len * a) l = mid;
        else r = mid;
    }

    for (int i = 0; i < m; i++)
        q[i] = 1;
    q[r] = 0;

    for (int i = 0; i < m; i++) {
        if (i == r)
            continue;

        gr[u[i]].pb({v[i], i});
        gr[v[i]].pb({u[i], i});
    }

    vector <int> left, right;
    for (int i = 0; i < n; i++)
        from[i] = -1;
    from[u[r]] = u[r];
    from[v[r]] = v[r];

    queue <int> qu;
    qu.push(u[r]);
    qu.push(v[r]);

    while (!qu.empty()) {
        int ver = qu.front();
        qu.pop();

        for (auto &[to, id] : gr[ver]) {
            if (from[to] != -1)
                continue;

            from[to] = from[ver];
            dist[to] = dist[ver] + 1;
            if (from[to] == u[r]) left.pb(id);
            else right.pb(id);

            q[id] = 0;
            qu.push(to);
        }
    }

    vector <int> now;
    int s = u[r], t = v[r];

    now = q;
    for (int i : left)
        now[i] = 1;

    int len_left = ask(now);
    l = -2, r = left.size();
    while (l + 1 < r) {
        int mid = (l + r) >> 1;

        now = q;
        for (int i = 0; i <= mid; i++)
            now[left[i]] = 1;

        if (ask(now) == len_left) r = mid;
        else l = mid;
    }

    if (r != -1) {
        if (dist[u[left[r]]] > dist[v[left[r]]]) s = u[left[r]];
        else s = v[left[r]];
    }

    now = q;
    for (int i : right)
        now[i] = 1;

    int len_right = ask(now);
    l = -2, r = right.size();
    while (l + 1 < r) {
        int mid = (l + r) >> 1;

        now = q;
        for (int i = 0; i <= mid; i++)
            now[right[i]] = 1;

        if (ask(now) == len_right) r = mid;
        else l = mid;
    }

    if (r != -1) {
        if (dist[u[right[r]]] > dist[v[right[r]]]) t = u[right[r]];
        else t = v[right[r]];
    }

    answer(s, t);
    return;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 2904 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 2904 KB Output is correct
12 Correct 1 ms 3000 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 8 ms 3672 KB Output is correct
3 Correct 82 ms 9268 KB Output is correct
4 Correct 76 ms 9268 KB Output is correct
5 Correct 78 ms 9412 KB Output is correct
6 Correct 76 ms 9400 KB Output is correct
7 Correct 81 ms 9276 KB Output is correct
8 Correct 72 ms 9280 KB Output is correct
9 Correct 75 ms 9412 KB Output is correct
10 Correct 77 ms 9264 KB Output is correct
11 Correct 76 ms 8684 KB Output is correct
12 Correct 78 ms 8724 KB Output is correct
13 Correct 77 ms 8708 KB Output is correct
14 Incorrect 84 ms 8920 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3672 KB Output is correct
2 Correct 15 ms 4260 KB Output is correct
3 Correct 21 ms 4888 KB Output is correct
4 Correct 66 ms 8756 KB Output is correct
5 Correct 64 ms 8768 KB Output is correct
6 Correct 67 ms 8672 KB Output is correct
7 Correct 69 ms 8596 KB Output is correct
8 Correct 68 ms 9260 KB Output is correct
9 Runtime error 67 ms 17140 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 8 ms 3804 KB Output is correct
3 Correct 50 ms 7900 KB Output is correct
4 Correct 80 ms 9264 KB Output is correct
5 Correct 69 ms 9128 KB Output is correct
6 Correct 69 ms 9276 KB Output is correct
7 Correct 70 ms 9532 KB Output is correct
8 Correct 66 ms 9252 KB Output is correct
9 Incorrect 79 ms 9256 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 Incorrect 10 ms 3672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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