oj.uz

답안 #1017006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017006 2024-07-08T17:03:09 Z vyshniak_n 통행료 (IOI18_highway) C++17
51 / 100
 99 ms 9800 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);
    ll len = ask(q);

    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) 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;

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

        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;

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

        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

# 결과 실행 시간 메모리 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 2 ms 3104 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
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 8 ms 3672 KB Output is correct
3 Correct 85 ms 9256 KB Output is correct
4 Correct 86 ms 9564 KB Output is correct
5 Correct 88 ms 9268 KB Output is correct
6 Correct 75 ms 9256 KB Output is correct
7 Correct 82 ms 9360 KB Output is correct
8 Correct 72 ms 9268 KB Output is correct
9 Correct 72 ms 9264 KB Output is correct
10 Correct 78 ms 9456 KB Output is correct
11 Correct 72 ms 8692 KB Output is correct
12 Correct 79 ms 8716 KB Output is correct
13 Correct 80 ms 8716 KB Output is correct
14 Correct 99 ms 8732 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 3672 KB Output is correct
2 Correct 15 ms 4184 KB Output is correct
3 Correct 21 ms 4896 KB Output is correct
4 Correct 63 ms 8760 KB Output is correct
5 Correct 80 ms 8652 KB Output is correct
6 Correct 69 ms 8676 KB Output is correct
7 Correct 67 ms 8664 KB Output is correct
8 Correct 62 ms 8624 KB Output is correct
9 Correct 67 ms 8664 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 8 ms 3828 KB Output is correct
3 Correct 55 ms 7880 KB Output is correct
4 Correct 73 ms 9256 KB Output is correct
5 Correct 70 ms 9260 KB Output is correct
6 Correct 70 ms 9460 KB Output is correct
7 Correct 73 ms 9284 KB Output is correct
8 Correct 59 ms 9384 KB Output is correct
9 Correct 88 ms 9704 KB Output is correct
10 Correct 80 ms 9516 KB Output is correct
11 Correct 84 ms 8680 KB Output is correct
12 Correct 82 ms 8696 KB Output is correct
13 Correct 82 ms 8680 KB Output is correct
14 Correct 82 ms 9164 KB Output is correct
15 Correct 68 ms 9268 KB Output is correct
16 Correct 78 ms 9216 KB Output is correct
17 Correct 86 ms 8984 KB Output is correct
18 Correct 87 ms 8700 KB Output is correct
19 Correct 70 ms 9156 KB Output is correct
20 Correct 72 ms 8648 KB Output is correct
21 Correct 68 ms 9788 KB Output is correct
22 Correct 65 ms 9792 KB Output is correct
23 Correct 75 ms 9644 KB Output is correct
24 Correct 73 ms 9800 KB Output is correct
25 Correct 82 ms 8856 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 3672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 3672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -