oj.uz

Submission #1060062

# Submission time Handle Problem Language Result Execution time Memory
1060062 2024-08-15T10:22:09 Z jerzyk Highway Tolls (IOI18_highway) C++17
90 / 100
 194 ms 61788 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 1000 * 1000 * 1000 * 2;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll bas, A, B;
vector<int>ed[N], num[N];
vector<int> cnd;
int dis[N];
vector<int> cur;

bool Question(int pos)
{
    for(int i = pos; i < (int)cur.size(); ++i)
    {
        int v = cur[i];
        for(int j = 0; j < (int)num[v].size(); ++j)
            cnd[num[v][j]] = 1;
    }
    ll ans = ask(cnd);
    for(int i = 0; i < (int)cnd.size(); ++i)
        cnd[i] = 0;
    return (ans > bas);
}

int BS()
{
    int p = 0, k = (int)cur.size(), s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Question(s))
            p = s;
        else
            k = s - 1;
    }
    return cur[p];
}

void BFS(int s, int n)
{
    int v; queue<int> q;
    for(int i = 0; i <= n; ++i)
        dis[i] = II;
    dis[s] = 0;
    q.push(s);
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(dis[ed[v][i]] > dis[v] + 1)
            {
                dis[ed[v][i]] = dis[v] + 1;
                q.push(ed[v][i]);
            }
        }
    }
}

void DoCur1(int n)
{
    vector<pair<int, int>> hlp;
    for(int i = 0; i < n; ++i)
        hlp.pb(make_pair(dis[i], i));
    sort(hlp.begin(), hlp.end());
    cur.clear();
    for(int i = 0; i < n; ++i)
        cur.pb(hlp[i].nd);
    /*cerr << "cur1 \n";
    for(int i = 0; i < n; ++i)
        cout << cur[i] << " ";
    cout << "\n";*/
}

void DoCur2(int n, int il)
{
    cur.clear();
    for(int i = 0; i < n; ++i)
        if(dis[i] == il)
            cur.pb(i);
}

void find_pair(int N, vector<int> U, vector<int> V, int XA, int XB)
{
    A = XA; B = XB;
    int n = N;
    for(int i = 0; i < (int)U.size(); ++i)
    {
        ed[U[i]].pb(V[i]); ed[V[i]].pb(U[i]);
        num[U[i]].pb(i); num[V[i]].pb(i);
        cnd.pb(0);
    }
    bas = ask(cnd);
    for(int i = 0; i < n; ++i)
        cur.pb(i);
    int mid = BS(), s, t;
    //cerr << mid << "\n";
    BFS(mid, n);
    DoCur1(n);
    s = BS();
    //cerr << s << "\n";
    BFS(s, n);
    DoCur2(n, bas / A);
    t = BS();
    answer(s, t);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 48984 KB Output is correct
2 Correct 19 ms 50264 KB Output is correct
3 Correct 129 ms 58584 KB Output is correct
4 Correct 122 ms 58508 KB Output is correct
5 Correct 124 ms 58644 KB Output is correct
6 Correct 111 ms 58440 KB Output is correct
7 Correct 132 ms 58604 KB Output is correct
8 Correct 121 ms 58456 KB Output is correct
9 Correct 121 ms 58592 KB Output is correct
10 Correct 135 ms 58596 KB Output is correct
11 Correct 114 ms 58468 KB Output is correct
12 Correct 130 ms 58272 KB Output is correct
13 Correct 113 ms 58292 KB Output is correct
14 Correct 123 ms 58128 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 50264 KB Output is correct
2 Correct 29 ms 51236 KB Output is correct
3 Correct 32 ms 52092 KB Output is correct
4 Correct 85 ms 58168 KB Output is correct
5 Correct 85 ms 58296 KB Output is correct
6 Correct 77 ms 58108 KB Output is correct
7 Correct 84 ms 58300 KB Output is correct
8 Correct 87 ms 58284 KB Output is correct
9 Correct 92 ms 58492 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 48984 KB Output is correct
2 Correct 19 ms 50248 KB Output is correct
3 Correct 100 ms 56944 KB Output is correct
4 Correct 137 ms 58444 KB Output is correct
5 Correct 122 ms 58380 KB Output is correct
6 Correct 117 ms 58412 KB Output is correct
7 Correct 126 ms 58364 KB Output is correct
8 Correct 124 ms 58560 KB Output is correct
9 Correct 121 ms 58480 KB Output is correct
10 Correct 138 ms 58612 KB Output is correct
11 Correct 120 ms 58292 KB Output is correct
12 Correct 115 ms 58276 KB Output is correct
13 Correct 118 ms 58264 KB Output is correct
14 Correct 120 ms 58124 KB Output is correct
15 Correct 134 ms 58576 KB Output is correct
16 Correct 122 ms 58604 KB Output is correct
17 Correct 114 ms 58228 KB Output is correct
18 Correct 123 ms 58128 KB Output is correct
19 Correct 123 ms 58360 KB Output is correct
20 Correct 115 ms 58228 KB Output is correct
21 Correct 117 ms 58888 KB Output is correct
22 Correct 106 ms 58848 KB Output is correct
23 Correct 109 ms 59316 KB Output is correct
24 Correct 106 ms 59384 KB Output is correct
25 Correct 111 ms 58488 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 50256 KB Output is correct
2 Correct 22 ms 50264 KB Output is correct
3 Correct 143 ms 58884 KB Output is correct
4 Correct 155 ms 59076 KB Output is correct
5 Correct 171 ms 61788 KB Output is correct
6 Correct 165 ms 61484 KB Output is correct
7 Correct 154 ms 61540 KB Output is correct
8 Correct 171 ms 61528 KB Output is correct
9 Correct 109 ms 55396 KB Output is correct
10 Correct 145 ms 56424 KB Output is correct
11 Correct 121 ms 56776 KB Output is correct
12 Correct 177 ms 58804 KB Output is correct
13 Correct 170 ms 61012 KB Output is correct
14 Correct 165 ms 61320 KB Output is correct
15 Correct 155 ms 61348 KB Output is correct
16 Correct 147 ms 57260 KB Output is correct
17 Correct 118 ms 60996 KB Output is correct
18 Correct 123 ms 61024 KB Output is correct
19 Correct 116 ms 61012 KB Output is correct
20 Correct 121 ms 61168 KB Output is correct
21 Correct 158 ms 61360 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 50140 KB Output is correct
2 Correct 20 ms 50260 KB Output is correct
3 Correct 139 ms 60660 KB Output is correct
4 Correct 135 ms 60852 KB Output is correct
5 Correct 151 ms 60800 KB Output is correct
6 Correct 181 ms 61776 KB Output is correct
7 Correct 134 ms 60640 KB Output is correct
8 Correct 148 ms 60664 KB Output is correct
9 Correct 159 ms 60888 KB Output is correct
10 Correct 183 ms 61580 KB Output is correct
11 Correct 175 ms 61572 KB Output is correct
12 Correct 188 ms 61432 KB Output is correct
13 Correct 123 ms 56820 KB Output is correct
14 Correct 130 ms 56364 KB Output is correct
15 Correct 120 ms 56704 KB Output is correct
16 Correct 125 ms 56356 KB Output is correct
17 Correct 125 ms 56820 KB Output is correct
18 Correct 125 ms 56416 KB Output is correct
19 Correct 151 ms 60640 KB Output is correct
20 Correct 162 ms 60960 KB Output is correct
21 Correct 161 ms 61340 KB Output is correct
22 Correct 169 ms 61288 KB Output is correct
23 Correct 182 ms 61216 KB Output is correct
24 Correct 166 ms 61260 KB Output is correct
25 Correct 194 ms 61200 KB Output is correct
26 Correct 184 ms 61284 KB Output is correct
27 Correct 110 ms 61196 KB Output is correct
28 Partially correct 128 ms 60904 KB Output is partially correct
29 Partially correct 121 ms 61252 KB Output is partially correct
30 Correct 134 ms 60992 KB Output is correct
31 Partially correct 118 ms 60932 KB Output is partially correct
32 Partially correct 120 ms 60912 KB Output is partially correct
33 Partially correct 126 ms 61196 KB Output is partially correct
34 Partially correct 119 ms 61144 KB Output is partially correct
35 Partially correct 118 ms 61172 KB Output is partially correct
36 Partially correct 111 ms 60848 KB Output is partially correct
37 Partially correct 122 ms 61252 KB Output is partially correct
38 Correct 125 ms 61056 KB Output is correct
39 Correct 158 ms 61232 KB Output is correct
40 Correct 163 ms 61332 KB Output is correct
41 Correct 163 ms 61372 KB Output is correct
42 Correct 171 ms 61452 KB Output is correct