oj.uz

Submission #1016953

# Submission time Handle Problem Language Result Execution time Memory
1016953 2024-07-08T16:06:30 Z vyshniak_n Highway Tolls (IOI18_highway) C++17
5 / 100
 86 ms 17084 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;
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 3092 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 2904 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 7 ms 3812 KB Output is correct
3 Correct 84 ms 9476 KB Output is correct
4 Correct 78 ms 9264 KB Output is correct
5 Correct 79 ms 9276 KB Output is correct
6 Correct 86 ms 9260 KB Output is correct
7 Correct 79 ms 9296 KB Output is correct
8 Correct 77 ms 9624 KB Output is correct
9 Correct 70 ms 9272 KB Output is correct
10 Correct 83 ms 9260 KB Output is correct
11 Correct 75 ms 8792 KB Output is correct
12 Correct 76 ms 8716 KB Output is correct
13 Correct 72 ms 8728 KB Output is correct
14 Incorrect 83 ms 8772 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 14 ms 4184 KB Output is correct
3 Correct 21 ms 4924 KB Output is correct
4 Correct 61 ms 8660 KB Output is correct
5 Correct 66 ms 8768 KB Output is correct
6 Correct 63 ms 8684 KB Output is correct
7 Correct 65 ms 8600 KB Output is correct
8 Correct 69 ms 8648 KB Output is correct
9 Runtime error 67 ms 17084 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 1 ms 3160 KB Output is correct
2 Correct 8 ms 3684 KB Output is correct
3 Correct 67 ms 7896 KB Output is correct
4 Correct 69 ms 9256 KB Output is correct
5 Correct 72 ms 9424 KB Output is correct
6 Correct 69 ms 9256 KB Output is correct
7 Correct 75 ms 9256 KB Output is correct
8 Correct 72 ms 9244 KB Output is correct
9 Incorrect 79 ms 9272 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 9 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 10 ms 3672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -