oj.uz

Submission #802458

# Submission time Handle Problem Language Result Execution time Memory
802458 2023-08-02T12:21:45 Z boris_mihov Highway Tolls (IOI18_highway) C++17
51 / 100
 134 ms 18260 KB 
#include "highway.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <numeric>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 90000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, m, a, b;
std::queue <int> q;
std::vector <std::pair <int,int>> g[MAXN];
std::vector <std::pair <int,int>> t1[MAXN];
std::vector <std::pair <int,int>> t2[MAXN];
std::vector <int> edgeU;
std::vector <int> edgeV;
int inTree[MAXN];
bool vis[MAXN];
int par[MAXN];

int find(std::vector <std::pair <int,int>> t[], int root, int cnt, int cnt2)
{
    // std::cout << "find: " << root << ' ' << cnt << ' ' << cnt2 << '\n' << std::flush;
    if (cnt == 0)
    {
        return root;
    }

    while (!q.empty())
    {
        q.pop();
    }

    std::vector <int> order;
    q.push(root);

    while (!q.empty())
    {
        int top = q.front();
        q.pop();

        for (const auto &[u, idx] : t[top])
        {
            // if (root == 90) std::cout << "here: " << top << ' ' << u << ' ' << par[u] << '\n';
            if (u != par[top])
            {
                order.push_back(idx);
                q.push(u);
            }
        }
    }

    std::vector <int> w(m);
    int l = -1, r = order.size(), mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        std::fill(w.begin(), w.end(), 1);

        for (int i = 0 ; i <= mid ; ++i)
        {
            w[order[i]] = 0;
        }

        llong res = ask(w);
        // std::cout << "here: " << l << ' ' << r << ' ' << mid << " = " << res << ' ' << 1LL * a * cnt + 1LL * b * cnt2 << '\n';        
        if (res > 1LL * a * cnt + 1LL * b * cnt2) l = mid;
        else r = mid;
    }
    
    std::fill(w.begin(), w.end(), 1);
    for (int i = 0 ; i < order.size() ; ++i)
    {
        w[order[i]] = 0;
    }

    llong res = ask(w);
    // std::cout << "res: " << res << ' ' << edgeU[order[0]] << ' ' << edgeV[order[0]] << '\n';
    // while (res != 1LL * cnt * a + 1LL * cnt2 * b || r == order.size());
    assert(r < order.size());
    int u = edgeU[order[r]];
    int v = edgeV[order[r]];
    if (par[v] == u)
    {
        std::swap(u, v);
    }

    return u;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) 
{
    n = N;
    m = U.size();
    a = A; b = B;
    edgeU = U;
    edgeV = V;

    for (int i = 0 ; i < m ; ++i)
    {
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
    }

    std::vector <int> toAsk(m, 0);
    llong res = ask(toAsk);

    int l = -1, r = m, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        std::fill(toAsk.begin(), toAsk.end(), 0);
        for (int i = 0 ; i <= mid ; ++i)
        {
            toAsk[i] = 1;
        }

        llong curr = ask(toAsk);
        if (curr == res) l = mid;
        else r = mid;
    }


    assert(r < m);
    int rootOne = U[r];
    int rootTwo = V[r];
    par[rootOne] = par[rootTwo] = -1;
    // std::cout << "lying on path: " << rootOne << ' ' << rootTwo << '\n';
    inTree[rootOne] = 1;
    inTree[rootTwo] = 2;
    vis[rootOne] = true;
    vis[rootTwo] = true;
    q.push(rootOne);
    q.push(rootTwo);

    while (!q.empty())
    {
        int top = q.front();
        q.pop();

        // if (inTree[top] == 1) std::cout << "top: " << top << '\n';
        for (const auto &[u, idx] : g[top])
        {
            if (!vis[u])
            {
                par[u] = top;
                vis[u] = true;
                inTree[u] = inTree[top];
                if (inTree[top] == 1)
                {
                    t1[top].push_back({u, idx});
                    t1[u].push_back({top, idx});
                } else
                {
                    t2[top].push_back({u, idx});
                    t2[u].push_back({top, idx});
                }

                q.push(u);
            }
        }
    }       

    std::fill(toAsk.begin(), toAsk.end(), 0);
    for (int i = 0 ; i < n ; ++i)
    {
        for (const auto &[u, idx] : t1[i])
        {
            toAsk[idx] = 1;
        }
    }
    std::fill(toAsk.begin(), toAsk.end(), 0);
    for (int i = 0 ; i < n ; ++i)
    {
        for (const auto &[u, idx] : t1[i])
        {
            toAsk[idx] = 1;
        }
    }

    llong currRES = ask(toAsk);
    int cntEdges = (currRES - res) / (b - a);
    int cntEdges2 = res / a - cntEdges - 1;
    // std::cout << "cnt edges: " << cntEdges << ' ' << cntEdges2 << '\n';
    int s = find(t1, rootOne, cntEdges, cntEdges2 + 1);
    int t = find(t2, rootTwo, cntEdges2, cntEdges + 1);
    answer(s, t);
}

/*
9 12 1 10 1 3
0 1
1 2
2 6
6 3
3 4
4 0
0 5
5 6
6 7
7 0
0 8
8 6
*/

Compilation message

highway.cpp: In function 'int find(std::vector<std::pair<int, int> >*, int, int, int)':
highway.cpp:77:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0 ; i < order.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from highway.cpp:5:
highway.cpp:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     assert(r < order.size());
      |            ~~^~~~~~~~~~~~~~
highway.cpp:82:11: warning: unused variable 'res' [-Wunused-variable]
   82 |     llong res = ask(w);
      |           ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6712 KB Output is correct
2 Correct 15 ms 7808 KB Output is correct
3 Correct 102 ms 17476 KB Output is correct
4 Correct 107 ms 17500 KB Output is correct
5 Correct 98 ms 17588 KB Output is correct
6 Correct 131 ms 17476 KB Output is correct
7 Correct 108 ms 17516 KB Output is correct
8 Correct 126 ms 17508 KB Output is correct
9 Correct 118 ms 17484 KB Output is correct
10 Correct 120 ms 17516 KB Output is correct
11 Correct 131 ms 16304 KB Output is correct
12 Correct 129 ms 16304 KB Output is correct
13 Correct 109 ms 16456 KB Output is correct
14 Correct 122 ms 16424 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7744 KB Output is correct
2 Correct 28 ms 8816 KB Output is correct
3 Correct 32 ms 9748 KB Output is correct
4 Correct 101 ms 16240 KB Output is correct
5 Correct 95 ms 16252 KB Output is correct
6 Correct 92 ms 16252 KB Output is correct
7 Correct 86 ms 15956 KB Output is correct
8 Correct 103 ms 16264 KB Output is correct
9 Correct 68 ms 16124 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6680 KB Output is correct
2 Correct 25 ms 7748 KB Output is correct
3 Correct 101 ms 15468 KB Output is correct
4 Correct 104 ms 17512 KB Output is correct
5 Correct 96 ms 17480 KB Output is correct
6 Correct 109 ms 17500 KB Output is correct
7 Correct 95 ms 16992 KB Output is correct
8 Correct 97 ms 17500 KB Output is correct
9 Correct 115 ms 17732 KB Output is correct
10 Correct 103 ms 17480 KB Output is correct
11 Correct 99 ms 16372 KB Output is correct
12 Correct 118 ms 16352 KB Output is correct
13 Correct 119 ms 16316 KB Output is correct
14 Correct 134 ms 16256 KB Output is correct
15 Correct 88 ms 17520 KB Output is correct
16 Correct 85 ms 17484 KB Output is correct
17 Correct 127 ms 16352 KB Output is correct
18 Correct 107 ms 16404 KB Output is correct
19 Correct 86 ms 17496 KB Output is correct
20 Correct 98 ms 16376 KB Output is correct
21 Correct 104 ms 18260 KB Output is correct
22 Correct 85 ms 18196 KB Output is correct
23 Correct 102 ms 17928 KB Output is correct
24 Correct 119 ms 17784 KB Output is correct
25 Correct 126 ms 16544 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7848 KB Output is correct
2 Incorrect 15 ms 7888 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 15828 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -