oj.uz

Submission #893952

# Submission time Handle Problem Language Result Execution time Memory
893952 2023-12-27T17:42:11 Z borisAngelov Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 36208 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 level, int l, int r, vector<Query>& curr)
{
    if (level > 20)
    {
        return;
    }

    if (l > r)
    {
        return;
    }

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

    if (l == r)
    {
        for (int i = 0; i < curr.size(); ++i)
        {
            answers[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<Query> toLeft;
    vector<Query> toRight;

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

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

vector<long long> uniqueDistances()
{
    set<long long> s;
    vector<long long> res;

    for (int i = 1; i <= n; ++i)
    {
        if (s.find(dist[i]) == s.end())
        {
            s.insert(dist[i]);
        }
    }

    for (auto element : s)
    {
        res.push_back(element);
    }

    return res;
}

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));
            }
        }
    }

    /*cout << "check " << endl;

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

    cout << endl;*/

    toTry = uniqueDistances();

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < g[i].size(); ++j)
        {
            if (i < g[i][j].first)
            {
                long long d = min(dist[i], dist[g[i][j].first]);

                int l = 0;
                int r = toTry.size() - 1;

                while (l <= r)
                {
                    int mid = (l + r) / 2;

                    if (toTry[mid] >= d)
                    {
                        r = mid - 1;
                    }
                    else
                    {
                        l = mid + 1;
                    }
                }

                byValue[l].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();

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

    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, int, std::vector<Query>&)':
plan.cpp:141:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for (int i = 0; i < curr.size(); ++i)
      |                         ~~^~~~~~~~~~~~~
plan.cpp:153: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]
  153 |         for (int j = 0; j < byValue[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~
plan.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int i = 0; i < curr.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:249: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]
  249 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp:275: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]
  275 |         for (int j = 0; j < g[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 3 ms 7512 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 5 ms 7672 KB Output is correct
10 Correct 2 ms 7512 KB Output is correct
11 Correct 8 ms 7516 KB Output is correct
12 Correct 2 ms 7728 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 5 ms 7512 KB Output is correct
15 Correct 8 ms 7516 KB Output is correct
16 Correct 3415 ms 18992 KB Output is correct
17 Correct 2388 ms 36208 KB Output is correct
18 Correct 221 ms 10132 KB Output is correct
19 Correct 76 ms 29764 KB Output is correct
20 Correct 2539 ms 36136 KB Output is correct
21 Correct 300 ms 31428 KB Output is correct
22 Execution timed out 4083 ms 19916 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7768 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 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 7512 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 132 ms 18152 KB Output is correct
2 Correct 285 ms 30492 KB Output is correct
3 Correct 262 ms 30408 KB Output is correct
4 Correct 92 ms 16396 KB Output is correct
5 Correct 281 ms 30912 KB Output is correct
6 Correct 274 ms 29524 KB Output is correct
7 Correct 262 ms 30568 KB Output is correct
8 Correct 251 ms 29788 KB Output is correct
9 Correct 267 ms 29632 KB Output is correct
10 Correct 278 ms 30512 KB Output is correct
11 Correct 319 ms 30488 KB Output is correct
12 Correct 267 ms 30612 KB Output is correct
13 Correct 314 ms 30268 KB Output is correct
14 Correct 279 ms 29896 KB Output is correct
15 Correct 268 ms 31424 KB Output is correct
16 Correct 307 ms 30264 KB Output is correct
17 Correct 259 ms 29632 KB Output is correct
18 Correct 258 ms 29896 KB Output is correct
19 Correct 90 ms 16356 KB Output is correct
20 Correct 295 ms 30408 KB Output is correct
21 Correct 213 ms 28880 KB Output is correct
22 Correct 53 ms 15420 KB Output is correct
23 Correct 126 ms 15564 KB Output is correct
24 Correct 51 ms 15172 KB Output is correct
25 Correct 50 ms 15424 KB Output is correct
26 Correct 109 ms 15244 KB Output is correct
27 Correct 93 ms 16352 KB Output is correct
28 Correct 52 ms 15304 KB Output is correct
29 Correct 98 ms 16336 KB Output is correct
30 Correct 51 ms 15184 KB Output is correct
31 Correct 101 ms 16304 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 3 ms 7512 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 5 ms 7672 KB Output is correct
10 Correct 2 ms 7512 KB Output is correct
11 Correct 8 ms 7516 KB Output is correct
12 Correct 2 ms 7728 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 5 ms 7512 KB Output is correct
15 Correct 8 ms 7516 KB Output is correct
16 Correct 3415 ms 18992 KB Output is correct
17 Correct 2388 ms 36208 KB Output is correct
18 Correct 221 ms 10132 KB Output is correct
19 Correct 76 ms 29764 KB Output is correct
20 Correct 2539 ms 36136 KB Output is correct
21 Correct 300 ms 31428 KB Output is correct
22 Execution timed out 4083 ms 19916 KB Time limit exceeded
23 Halted 0 ms 0 KB -