oj.uz

Submission #743590

# Submission time Handle Problem Language Result Execution time Memory
743590 2023-05-17T14:13:58 Z danikoynov Highway Tolls (IOI18_highway) C++14
100 / 100
 254 ms 18372 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
vector < pair < int, int > > g[maxn];
int n, m;
ll a, b;
pair < int, int > ed[maxn];

vector < int > turn_active(vector < int > act)
{
    vector < int > res(m, 1);
    for (int v : act)
        res[v] = 0;
    return res;
}
vector < int > turn_inactive(vector < int > act)
{
    vector < int > res(m, 0);
    for (int v : act)
        res[v] = 1;
    return res;
}
int mark[maxn], from[maxn], dis[maxn];
int used[maxn], sp[maxn];
int sub_solve(int s, vector < int > st, ll sum, int idx)
{
    for (int i = 0; i < m; i ++)
        used[i] = 1e9, sp[i] = 0;
    for (int v : st)
        used[v] = -1;
    used[s] = 0;
    queue < int > q;
    q.push(s);
    from[s] = -1;
    vector < int > d;
    vector < int > base;
    ///exit(0);
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        d.push_back(v);
        for (pair < int, int > nb : g[v])
        {
            if (used[nb.first] == -1)
            {
                used[nb.first] = used[v] + 1;
                from[nb.first] = nb.second;
                sp[nb.second] = 1;
                base.push_back(nb.second);
                q.push(nb.first);
            }
        }
    }

    vector < int > forb;
    if (m != n - 1)
    {

    for (int i = 0; i < m; i ++)
    {
        if (i == idx)
            continue;
        if (used[ed[i].first] != 1e9 && used[ed[i].second] != 1e9 && sp[i] == 0)
            forb.push_back(i);
        else
        if (used[ed[i].first] == 1e9 && used[ed[i].second] != 1e9)
            forb.push_back(i);
        else
        if (used[ed[i].first] != 1e9 && used[ed[i].second] == 1e9)
            forb.push_back(i);
    }
    }
    int lf = 1, rf = (int)(d.size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        vector < int > cur_set;
        for (int i = max(1,mf); i < d.size(); i ++)
            cur_set.push_back(from[d[i]]);
        for (int v : forb)
            cur_set.push_back(v);
        if (ask(turn_inactive(cur_set)) != sum)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    return d[rf];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    n = N;
    m = U.size();
    a = A;
    b = B;
    for (int i = 0; i < m; i ++)
    {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
        ed[i] = {U[i], V[i]};
    }


    vector < int > act;
    for (int i = 0; i < m; i ++)
    act.push_back(i);

    ll base_sum = ask(turn_active(act));
    ll num_edges = base_sum / (ll)(A);
    int lf = 0, rf = m - 1;
    while(lf <= rf)
    {
        vector < int > cur;
        int mf = (lf + rf) / 2;
        for (int i = 0; i <= mf; i ++)
            cur.push_back(i);

        if (ask(turn_inactive(cur)) != num_edges * (ll)(A))
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    vector < int > ch;
    ch.push_back(lf);
    int edge = lf;
    ///cout << "here " << edge << endl;
    int v = V[edge], u = U[edge];

    queue < int > q;
    mark[v] = 1;
    mark[u] = 2;
    q.push(v);
    q.push(u);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        ///cout << cur << " : " << mark[cur] << endl;
        for (pair < int, int > nb : g[cur])
        {
            if (mark[nb.first] == 0)
            {
                mark[nb.first] = mark[cur];
                q.push(nb.first);
            }
        }
    }
    vector < int > set_s, set_t;
    for (int i = 0; i < n; i ++)
    {
        if (mark[i] == 1)
            set_s.push_back(i);
        else
            set_t.push_back(i);
    }
    int S = sub_solve(v, set_s, base_sum, edge), T = sub_solve(u, set_t, base_sum, edge);
    ///cout << S << " " << T << " : " << v << " " << u << endl;
    answer(S, T);
}

Compilation message

highway.cpp: In function 'int sub_solve(int, std::vector<int>, ll, int)':
highway.cpp:82:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int i = max(1,mf); i < d.size(); i ++)
      |                                 ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5020 KB Output is correct
8 Correct 3 ms 4944 KB Output is correct
9 Correct 3 ms 5120 KB Output is correct
10 Correct 4 ms 5044 KB Output is correct
11 Correct 3 ms 5016 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5080 KB Output is correct
2 Correct 13 ms 6096 KB Output is correct
3 Correct 130 ms 14888 KB Output is correct
4 Correct 118 ms 14640 KB Output is correct
5 Correct 129 ms 14672 KB Output is correct
6 Correct 141 ms 14696 KB Output is correct
7 Correct 128 ms 14800 KB Output is correct
8 Correct 160 ms 15492 KB Output is correct
9 Correct 124 ms 15356 KB Output is correct
10 Correct 142 ms 14672 KB Output is correct
11 Correct 135 ms 13988 KB Output is correct
12 Correct 144 ms 14344 KB Output is correct
13 Correct 142 ms 14072 KB Output is correct
14 Correct 141 ms 14036 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6096 KB Output is correct
2 Correct 36 ms 7052 KB Output is correct
3 Correct 41 ms 8236 KB Output is correct
4 Correct 133 ms 13628 KB Output is correct
5 Correct 116 ms 13712 KB Output is correct
6 Correct 126 ms 13868 KB Output is correct
7 Correct 158 ms 14608 KB Output is correct
8 Correct 105 ms 13460 KB Output is correct
9 Correct 102 ms 14512 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5084 KB Output is correct
2 Correct 17 ms 6092 KB Output is correct
3 Correct 118 ms 12920 KB Output is correct
4 Correct 167 ms 14880 KB Output is correct
5 Correct 140 ms 15364 KB Output is correct
6 Correct 180 ms 15120 KB Output is correct
7 Correct 169 ms 14964 KB Output is correct
8 Correct 163 ms 15368 KB Output is correct
9 Correct 157 ms 14636 KB Output is correct
10 Correct 175 ms 14672 KB Output is correct
11 Correct 152 ms 14240 KB Output is correct
12 Correct 129 ms 13932 KB Output is correct
13 Correct 137 ms 14332 KB Output is correct
14 Correct 189 ms 13916 KB Output is correct
15 Correct 125 ms 14988 KB Output is correct
16 Correct 172 ms 15404 KB Output is correct
17 Correct 142 ms 14032 KB Output is correct
18 Correct 166 ms 14176 KB Output is correct
19 Correct 125 ms 15384 KB Output is correct
20 Correct 150 ms 14544 KB Output is correct
21 Correct 95 ms 15228 KB Output is correct
22 Correct 93 ms 15252 KB Output is correct
23 Correct 123 ms 14508 KB Output is correct
24 Correct 112 ms 14144 KB Output is correct
25 Correct 127 ms 14092 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6096 KB Output is correct
2 Correct 17 ms 6352 KB Output is correct
3 Correct 133 ms 15504 KB Output is correct
4 Correct 150 ms 15740 KB Output is correct
5 Correct 200 ms 18372 KB Output is correct
6 Correct 167 ms 18156 KB Output is correct
7 Correct 184 ms 18148 KB Output is correct
8 Correct 187 ms 17808 KB Output is correct
9 Correct 148 ms 16004 KB Output is correct
10 Correct 178 ms 16268 KB Output is correct
11 Correct 159 ms 16664 KB Output is correct
12 Correct 225 ms 17536 KB Output is correct
13 Correct 184 ms 17604 KB Output is correct
14 Correct 254 ms 17912 KB Output is correct
15 Correct 228 ms 17980 KB Output is correct
16 Correct 172 ms 16412 KB Output is correct
17 Correct 100 ms 15080 KB Output is correct
18 Correct 116 ms 15420 KB Output is correct
19 Correct 139 ms 15288 KB Output is correct
20 Correct 107 ms 15532 KB Output is correct
21 Correct 175 ms 18152 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6160 KB Output is correct
2 Correct 16 ms 6212 KB Output is correct
3 Correct 195 ms 15720 KB Output is correct
4 Correct 173 ms 15884 KB Output is correct
5 Correct 154 ms 16548 KB Output is correct
6 Correct 189 ms 17836 KB Output is correct
7 Correct 119 ms 15864 KB Output is correct
8 Correct 176 ms 16412 KB Output is correct
9 Correct 169 ms 16092 KB Output is correct
10 Correct 240 ms 18036 KB Output is correct
11 Correct 218 ms 17888 KB Output is correct
12 Correct 198 ms 17748 KB Output is correct
13 Correct 211 ms 16652 KB Output is correct
14 Correct 154 ms 16208 KB Output is correct
15 Correct 130 ms 16760 KB Output is correct
16 Correct 184 ms 16248 KB Output is correct
17 Correct 197 ms 16512 KB Output is correct
18 Correct 160 ms 16312 KB Output is correct
19 Correct 189 ms 17396 KB Output is correct
20 Correct 217 ms 17844 KB Output is correct
21 Correct 247 ms 18132 KB Output is correct
22 Correct 225 ms 18128 KB Output is correct
23 Correct 189 ms 17760 KB Output is correct
24 Correct 187 ms 17952 KB Output is correct
25 Correct 233 ms 17964 KB Output is correct
26 Correct 209 ms 17888 KB Output is correct
27 Correct 138 ms 15192 KB Output is correct
28 Correct 116 ms 15432 KB Output is correct
29 Correct 134 ms 15700 KB Output is correct
30 Correct 115 ms 15312 KB Output is correct
31 Correct 135 ms 15280 KB Output is correct
32 Correct 116 ms 15188 KB Output is correct
33 Correct 140 ms 15480 KB Output is correct
34 Correct 137 ms 15648 KB Output is correct
35 Correct 119 ms 15356 KB Output is correct
36 Correct 132 ms 15380 KB Output is correct
37 Correct 148 ms 15556 KB Output is correct
38 Correct 104 ms 15472 KB Output is correct
39 Correct 171 ms 18264 KB Output is correct
40 Correct 219 ms 18264 KB Output is correct
41 Correct 160 ms 17876 KB Output is correct
42 Correct 198 ms 17892 KB Output is correct