oj.uz

Submission #157045

# Submission time Handle Problem Language Result Execution time Memory
157045 2019-10-09T08:55:37 Z Alexa2001 Highway Tolls (IOI18_highway) C++17
90 / 100
 610 ms 19680 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Nmax = 150005;

vector<int> w, nodes;
vector<int> down[Nmax];
vector<pair<int,int>> edge[Nmax];

int n, m;



void dfs(int node)
{
    nodes.push_back(node);
    for(auto it : down[node])
        dfs(it);
}

int solve(int id, int root, ll cost, vector<int> &u, vector<int> &v)
{
    int i;
    for(i=0; i<n; ++i) edge[i].clear();
    for(i=0; i<n; ++i) down[i].clear();
    nodes.clear();

    for(i=0; i<=id; ++i)
    {
        edge[u[i]].push_back({ v[i], i });
        edge[v[i]].push_back({ u[i], i });
    }

    queue<int> q;
    q.push(root);

    vector<int> parent(n, -1);
    vector<int> dist(n, 1e9);

    parent[root] = root;
    dist[root] = 0;

    while(q.size())
    {
        int node = q.front();
        q.pop();

        for(auto it : edge[node])
            if(parent[it.first] == -1)
            {
                dist[it.first] = dist[node] + 1;
                parent[it.first] = node;
                q.push(it.first);
                down[node].push_back(it.first);
            }
    }

    dfs(root);

    int st, dr, mid;
    st = 0; dr = nodes.size() - 1;

    while(st <= dr)
    {
        mid = (st + dr) / 2;

        for(i=0; i<=id; ++i) w[i] = 0;
        for(; i<m; ++i) w[i] = 1;

        for(i=mid+1; i<nodes.size(); ++i)
            for(auto it : edge[nodes[i]])
                if(dist[it.first] < dist[nodes[i]])
                    w[it.second] = 1;

        if(cost == ask(w)) dr = mid - 1;
            else st = mid + 1;
    }
    assert(st < nodes.size() && st >= 0);
    return nodes[st];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
    n = N;
    m = U.size();
    w.resize(m, 0);

    int st, dr, mid;
    int i;

    ll initial_cost = ask(w);

    st = 1; dr = m;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        for(i=0; i<mid; ++i) w[i] = 0;
        for(; i<m; ++i) w[i] = 1;

        if(ask(w) == initial_cost) dr = mid - 1;
            else st = mid + 1;
    }

    /// indicele dr e special

    int X, Y;

    X = solve(dr, V[dr], initial_cost, U, V);
    Y = solve(dr, X, initial_cost, U, V);

    answer(X, Y);
}

Compilation message

highway.cpp: In function 'int solve(int, int, ll, std::vector<int>&, std::vector<int>&)':
highway.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=mid+1; i<nodes.size(); ++i)
                      ~^~~~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from highway.cpp:2:
highway.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(st < nodes.size() && st >= 0);
            ~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 8 ms 7372 KB Output is correct
5 Correct 8 ms 7448 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 8 ms 7444 KB Output is correct
8 Correct 9 ms 7288 KB Output is correct
9 Correct 9 ms 7336 KB Output is correct
10 Correct 9 ms 7288 KB Output is correct
11 Correct 9 ms 7336 KB Output is correct
12 Correct 8 ms 7416 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 29 ms 8172 KB Output is correct
3 Correct 274 ms 15012 KB Output is correct
4 Correct 367 ms 15024 KB Output is correct
5 Correct 327 ms 15028 KB Output is correct
6 Correct 323 ms 14268 KB Output is correct
7 Correct 254 ms 14564 KB Output is correct
8 Correct 225 ms 13464 KB Output is correct
9 Correct 237 ms 14092 KB Output is correct
10 Correct 333 ms 14820 KB Output is correct
11 Correct 287 ms 14848 KB Output is correct
12 Correct 267 ms 14700 KB Output is correct
13 Correct 477 ms 17152 KB Output is correct
14 Correct 446 ms 16884 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7848 KB Output is correct
2 Correct 46 ms 8752 KB Output is correct
3 Correct 69 ms 11336 KB Output is correct
4 Correct 192 ms 15904 KB Output is correct
5 Correct 188 ms 13816 KB Output is correct
6 Correct 190 ms 18564 KB Output is correct
7 Correct 213 ms 19680 KB Output is correct
8 Correct 186 ms 16764 KB Output is correct
9 Correct 201 ms 17792 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7468 KB Output is correct
2 Correct 33 ms 7948 KB Output is correct
3 Correct 220 ms 13208 KB Output is correct
4 Correct 261 ms 13824 KB Output is correct
5 Correct 350 ms 15180 KB Output is correct
6 Correct 216 ms 13864 KB Output is correct
7 Correct 176 ms 12224 KB Output is correct
8 Correct 243 ms 14604 KB Output is correct
9 Correct 362 ms 14632 KB Output is correct
10 Correct 304 ms 14092 KB Output is correct
11 Correct 318 ms 16952 KB Output is correct
12 Correct 512 ms 17332 KB Output is correct
13 Correct 312 ms 15104 KB Output is correct
14 Correct 372 ms 15788 KB Output is correct
15 Correct 277 ms 14136 KB Output is correct
16 Correct 363 ms 14456 KB Output is correct
17 Correct 344 ms 16952 KB Output is correct
18 Correct 390 ms 17148 KB Output is correct
19 Correct 182 ms 12084 KB Output is correct
20 Correct 196 ms 12844 KB Output is correct
21 Correct 212 ms 12764 KB Output is correct
22 Correct 205 ms 14024 KB Output is correct
23 Correct 261 ms 14784 KB Output is correct
24 Correct 261 ms 15152 KB Output is correct
25 Correct 316 ms 19532 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8172 KB Output is correct
2 Correct 45 ms 8440 KB Output is correct
3 Correct 425 ms 15684 KB Output is correct
4 Correct 461 ms 16016 KB Output is correct
5 Correct 359 ms 16248 KB Output is correct
6 Correct 471 ms 16376 KB Output is correct
7 Correct 540 ms 17060 KB Output is correct
8 Correct 509 ms 16036 KB Output is correct
9 Correct 230 ms 10240 KB Output is correct
10 Correct 255 ms 12792 KB Output is correct
11 Correct 277 ms 13268 KB Output is correct
12 Correct 459 ms 16168 KB Output is correct
13 Correct 367 ms 15568 KB Output is correct
14 Correct 410 ms 17304 KB Output is correct
15 Correct 436 ms 16984 KB Output is correct
16 Correct 308 ms 14384 KB Output is correct
17 Correct 329 ms 14720 KB Output is correct
18 Correct 246 ms 14296 KB Output is correct
19 Correct 296 ms 14704 KB Output is correct
20 Correct 321 ms 14664 KB Output is correct
21 Correct 549 ms 17312 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8104 KB Output is correct
2 Correct 46 ms 8396 KB Output is correct
3 Correct 487 ms 15628 KB Output is correct
4 Partially correct 360 ms 15708 KB Output is partially correct
5 Correct 378 ms 15916 KB Output is correct
6 Partially correct 456 ms 16576 KB Output is partially correct
7 Correct 343 ms 15668 KB Output is correct
8 Correct 362 ms 15412 KB Output is correct
9 Correct 399 ms 15920 KB Output is correct
10 Partially correct 486 ms 16960 KB Output is partially correct
11 Partially correct 610 ms 16956 KB Output is partially correct
12 Correct 410 ms 15888 KB Output is correct
13 Correct 232 ms 10300 KB Output is correct
14 Correct 233 ms 10308 KB Output is correct
15 Correct 268 ms 11136 KB Output is correct
16 Correct 266 ms 12712 KB Output is correct
17 Correct 261 ms 12992 KB Output is correct
18 Correct 272 ms 11432 KB Output is correct
19 Correct 350 ms 15016 KB Output is correct
20 Partially correct 387 ms 16752 KB Output is partially correct
21 Partially correct 453 ms 17068 KB Output is partially correct
22 Partially correct 508 ms 17112 KB Output is partially correct
23 Partially correct 479 ms 17056 KB Output is partially correct
24 Correct 524 ms 17064 KB Output is correct
25 Partially correct 499 ms 16732 KB Output is partially correct
26 Partially correct 446 ms 16864 KB Output is partially correct
27 Correct 243 ms 13420 KB Output is correct
28 Correct 329 ms 14624 KB Output is correct
29 Correct 232 ms 13272 KB Output is correct
30 Correct 247 ms 14152 KB Output is correct
31 Partially correct 386 ms 14728 KB Output is partially correct
32 Correct 342 ms 14704 KB Output is correct
33 Correct 204 ms 13876 KB Output is correct
34 Correct 218 ms 13720 KB Output is correct
35 Correct 400 ms 14844 KB Output is correct
36 Correct 220 ms 13060 KB Output is correct
37 Correct 304 ms 13900 KB Output is correct
38 Correct 280 ms 12636 KB Output is correct
39 Partially correct 561 ms 17628 KB Output is partially correct
40 Correct 423 ms 17648 KB Output is correct
41 Partially correct 520 ms 17188 KB Output is partially correct
42 Partially correct 520 ms 17176 KB Output is partially correct