oj.uz

Submission #893975

# Submission time Handle Problem Language Result Execution time Memory
893975 2023-12-27T18:09:58 Z borisAngelov Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 37024 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 61);

int n, m, k, q;

int startCities[maxn];

vector<pair<int, int>> g[maxn];

long long dist[maxn];

vector<long long> toTry;

struct Query
{
    int from;
    int to;
    int idx;

    Query()
    {

    }

    Query(int _from, int _to, int _idx)
    {
        from = _from;
        to = _to;
        idx = _idx;
    }
};

struct DSU
{
    struct Roll
    {
        int *pos;
        int val;
        int t;
    };

    int par[maxn];
    int dep[maxn];

    stack<Roll> rollback;

    void init()
    {
        while (!rollback.empty())
        {
            rollback.pop();
        }

        for (int i = 1; i <= n; ++i)
        {
            par[i] = i;
            dep[i] = 1;
        }
    }

    int root(int node)
    {
        if (node == par[node])
        {
            return node;
        }

        return root(par[node]);
    }

    void connect(int x, int y, int tim)
    {
        x = root(x);
        y = root(y);

        if (x == y)
        {
            return;
        }

        if (dep[x] < dep[y])
        {
            swap(x, y);
        }

        rollback.push({&par[y], par[y], tim});
        par[y] = x;

        if (dep[x] == dep[y])
        {
            rollback.push({&dep[x], dep[x], tim});
            ++dep[x];
        }
    }

    void rollbackSmaller(int tim)
    {
        while (!rollback.empty() && tim >= rollback.top().t)
        {
            *rollback.top().pos = rollback.top().val;
            rollback.pop();
        }
    }

    bool areConnected(int x, int y)
    {
        return root(x) == root(y);
    }
};

DSU dsu;

vector<Query> queries;
long long answers[maxn];

vector<pair<int, int>> byValue[maxn];

void parallelBinarySearch(int l, int r, vector<int>& curr)
{
    if (l > r)
    {
        return;
    }

    if (curr.empty())
    {
        return;
    }

    if (l == r)
    {
        for (int i = 0; i < curr.size(); ++i)
        {
            answers[queries[curr[i]].idx] = toTry[l];
        }

        return;
    }

    int mid = (l + r) / 2;

    for (int i = toTry.size() - 1; i >= mid + 1; --i)
    {
        for (int j = 0; j < byValue[i].size(); ++j)
        {
            dsu.connect(byValue[i][j].first, byValue[i][j].second, i);
        }
    }

    dsu.rollbackSmaller(mid);

    vector<int> toLeft;
    vector<int> toRight;

    for (int i = 0; i < curr.size(); ++i)
    {
        if (dsu.areConnected(queries[curr[i]].from, queries[curr[i]].to) == true)
        {
            toRight.push_back(curr[i]);
        }
        else
        {
            toLeft.push_back(curr[i]);
        }
    }

    parallelBinarySearch(l, mid, toLeft);
    parallelBinarySearch(mid + 1, r, toRight);
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    cin >> k;

    for (int i = 1; i <= k; ++i)
    {
        cin >> startCities[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
    }

    priority_queue<pair<long long, int>> pq;

    for (int i = 1; i <= k; ++i)
    {
        pq.push(make_pair(0, startCities[i]));
        dist[startCities[i]] = 0;
    }

    while (!pq.empty())
    {
        int node = pq.top().second;
        long long curr = -pq.top().first;
        pq.pop();

        for (int i = 0; i < g[node].size(); ++i)
        {
            long long path = g[node][i].second + curr;
            int to = g[node][i].first;

            if (dist[to] > path)
            {
                dist[to] = path;
                pq.push(make_pair(-path, to));
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        toTry.push_back(dist[i]);
    }

    sort(toTry.begin(), toTry.end());

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < g[i].size(); ++j)
        {
            long long d = min(dist[i], dist[g[i][j].first]);
            int idx = lower_bound(toTry.begin(), toTry.end(), d) - toTry.begin();
            byValue[idx].push_back(make_pair(i, g[i][j].first));
        }
    }

    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int from, to;
        cin >> from >> to;
        queries.push_back(Query(from, to, i));
    }

    dsu.init();

    vector<int> starting;

    for (int i = 0; i < q; ++i)
    {
        starting.push_back(i);
    }

    parallelBinarySearch(0, toTry.size() - 1, starting);

    for (int i = 1; i <= q; ++i)
    {
        cout << answers[i] << "\n";
    }

    return 0;
}

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

Compilation message

plan.cpp: In function 'void parallelBinarySearch(int, int, std::vector<int>&)':
plan.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for (int i = 0; i < curr.size(); ++i)
      |                         ~~^~~~~~~~~~~~~
plan.cpp:148:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for (int j = 0; j < byValue[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~
plan.cpp:159:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for (int i = 0; i < curr.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:223:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp:245:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |         for (int j = 0; j < g[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 7 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 2 ms 7512 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 7 ms 7516 KB Output is correct
15 Correct 7 ms 7516 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 7 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 2 ms 7512 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 7 ms 7516 KB Output is correct
15 Correct 7 ms 7516 KB Output is correct
16 Execution timed out 4024 ms 18488 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7260 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 1 ms 7260 KB Output is correct
9 Correct 1 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 21516 KB Output is correct
2 Correct 368 ms 36036 KB Output is correct
3 Correct 392 ms 36028 KB Output is correct
4 Correct 96 ms 16068 KB Output is correct
5 Correct 418 ms 36492 KB Output is correct
6 Correct 363 ms 35356 KB Output is correct
7 Correct 356 ms 35320 KB Output is correct
8 Correct 340 ms 35524 KB Output is correct
9 Correct 357 ms 35500 KB Output is correct
10 Correct 388 ms 36036 KB Output is correct
11 Correct 399 ms 36036 KB Output is correct
12 Correct 384 ms 36032 KB Output is correct
13 Correct 415 ms 36048 KB Output is correct
14 Correct 353 ms 35268 KB Output is correct
15 Correct 401 ms 37024 KB Output is correct
16 Correct 373 ms 35752 KB Output is correct
17 Correct 396 ms 35416 KB Output is correct
18 Correct 391 ms 35216 KB Output is correct
19 Correct 77 ms 15300 KB Output is correct
20 Correct 398 ms 35784 KB Output is correct
21 Correct 237 ms 36036 KB Output is correct
22 Correct 53 ms 17216 KB Output is correct
23 Correct 164 ms 16324 KB Output is correct
24 Correct 58 ms 17220 KB Output is correct
25 Correct 56 ms 17216 KB Output is correct
26 Correct 153 ms 16672 KB Output is correct
27 Correct 93 ms 16068 KB Output is correct
28 Correct 65 ms 17224 KB Output is correct
29 Correct 112 ms 16188 KB Output is correct
30 Correct 66 ms 17216 KB Output is correct
31 Correct 119 ms 16012 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 1 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 7 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 2 ms 7512 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 7 ms 7516 KB Output is correct
15 Correct 7 ms 7516 KB Output is correct
16 Execution timed out 4024 ms 18488 KB Time limit exceeded
17 Halted 0 ms 0 KB -