oj.uz

Submission #893966

# Submission time Handle Problem Language Result Execution time Memory
893966 2023-12-27T17:54:24 Z borisAngelov Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 36356 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)
    {
        if (rollback.size() > 200000)
        {
            exit(0);
        }
        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 (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; --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)
    {
        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:140:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for (int i = 0; i < curr.size(); ++i)
      |                         ~~^~~~~~~~~~~~~
plan.cpp:152: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]
  152 |         for (int j = 0; j < byValue[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~
plan.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i = 0; i < curr.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
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 i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp:271: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]
  271 |         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 7256 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 1 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 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 5 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 5 ms 7512 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 5 ms 7516 KB Output is correct
15 Correct 5 ms 7516 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 1 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 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 5 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 5 ms 7512 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 5 ms 7516 KB Output is correct
15 Correct 5 ms 7516 KB Output is correct
16 Correct 3255 ms 19088 KB Output is correct
17 Correct 2293 ms 36356 KB Output is correct
18 Correct 211 ms 10132 KB Output is correct
19 Correct 77 ms 29764 KB Output is correct
20 Correct 2435 ms 36216 KB Output is correct
21 Correct 304 ms 31688 KB Output is correct
22 Execution timed out 4080 ms 19788 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 1 ms 7768 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 1 ms 7516 KB Output is correct
6 Correct 1 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 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 116 ms 18012 KB Output is correct
2 Correct 269 ms 30624 KB Output is correct
3 Correct 263 ms 30288 KB Output is correct
4 Correct 92 ms 16336 KB Output is correct
5 Correct 272 ms 30912 KB Output is correct
6 Correct 266 ms 29896 KB Output is correct
7 Correct 262 ms 30564 KB Output is correct
8 Correct 242 ms 29636 KB Output is correct
9 Correct 275 ms 29708 KB Output is correct
10 Correct 268 ms 30648 KB Output is correct
11 Correct 281 ms 30604 KB Output is correct
12 Correct 273 ms 30832 KB Output is correct
13 Correct 261 ms 30404 KB Output is correct
14 Correct 253 ms 29860 KB Output is correct
15 Correct 267 ms 31804 KB Output is correct
16 Correct 268 ms 30428 KB Output is correct
17 Correct 302 ms 29520 KB Output is correct
18 Correct 254 ms 30024 KB Output is correct
19 Correct 91 ms 16592 KB Output is correct
20 Correct 266 ms 30404 KB Output is correct
21 Correct 200 ms 28812 KB Output is correct
22 Correct 61 ms 15348 KB Output is correct
23 Correct 114 ms 15564 KB Output is correct
24 Correct 49 ms 15428 KB Output is correct
25 Correct 49 ms 15424 KB Output is correct
26 Correct 96 ms 15056 KB Output is correct
27 Correct 87 ms 16332 KB Output is correct
28 Correct 51 ms 15424 KB Output is correct
29 Correct 107 ms 16336 KB Output is correct
30 Correct 49 ms 15428 KB Output is correct
31 Correct 88 ms 16332 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 1 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 2 ms 7516 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 5 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 5 ms 7512 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 5 ms 7516 KB Output is correct
15 Correct 5 ms 7516 KB Output is correct
16 Correct 3255 ms 19088 KB Output is correct
17 Correct 2293 ms 36356 KB Output is correct
18 Correct 211 ms 10132 KB Output is correct
19 Correct 77 ms 29764 KB Output is correct
20 Correct 2435 ms 36216 KB Output is correct
21 Correct 304 ms 31688 KB Output is correct
22 Execution timed out 4080 ms 19788 KB Time limit exceeded
23 Halted 0 ms 0 KB -