oj.uz

Submission #893980

# Submission time Handle Problem Language Result Execution time Memory
893980 2023-12-27T18:14:04 Z borisAngelov Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 36384 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];

set<pair<int, int>> s;

void parallelBinarySearch(int l, int r, vector<int>& curr)
{
    if (s.find(make_pair(l, r)) != s.end())
    {
        cout << "kur" << endl;
        exit(0);
    }
    s.insert({l, r});
    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:144:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for (int i = 0; i < curr.size(); ++i)
      |                         ~~^~~~~~~~~~~~~
plan.cpp:156: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]
  156 |         for (int j = 0; j < byValue[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~
plan.cpp:167:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for (int i = 0; i < curr.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:231: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]
  231 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp:253: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]
  253 |         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 7592 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 2 ms 7512 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 7512 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 8 ms 7648 KB Output is correct
15 Correct 7 ms 7512 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 7592 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 2 ms 7512 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 7512 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 8 ms 7648 KB Output is correct
15 Correct 7 ms 7512 KB Output is correct
16 Execution timed out 4093 ms 18892 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 3 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 7260 KB Output is correct
9 Correct 2 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 174 ms 21336 KB Output is correct
2 Correct 379 ms 35820 KB Output is correct
3 Correct 375 ms 35780 KB Output is correct
4 Correct 98 ms 16072 KB Output is correct
5 Correct 401 ms 36384 KB Output is correct
6 Correct 334 ms 35452 KB Output is correct
7 Correct 395 ms 35172 KB Output is correct
8 Correct 364 ms 35304 KB Output is correct
9 Correct 343 ms 35332 KB Output is correct
10 Correct 438 ms 36036 KB Output is correct
11 Correct 417 ms 36244 KB Output is correct
12 Correct 381 ms 36056 KB Output is correct
13 Correct 373 ms 35936 KB Output is correct
14 Correct 353 ms 35196 KB Output is correct
15 Correct 394 ms 36292 KB Output is correct
16 Correct 385 ms 35684 KB Output is correct
17 Correct 357 ms 35264 KB Output is correct
18 Correct 359 ms 35672 KB Output is correct
19 Correct 96 ms 15144 KB Output is correct
20 Correct 392 ms 35864 KB Output is correct
21 Correct 239 ms 35988 KB Output is correct
22 Correct 55 ms 17216 KB Output is correct
23 Correct 148 ms 16420 KB Output is correct
24 Correct 59 ms 17220 KB Output is correct
25 Correct 70 ms 17224 KB Output is correct
26 Correct 148 ms 16684 KB Output is correct
27 Correct 92 ms 16072 KB Output is correct
28 Correct 67 ms 17220 KB Output is correct
29 Correct 109 ms 16160 KB Output is correct
30 Correct 58 ms 17220 KB Output is correct
31 Correct 92 ms 16068 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 7592 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 2 ms 7512 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 7512 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 2 ms 7516 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 8 ms 7648 KB Output is correct
15 Correct 7 ms 7512 KB Output is correct
16 Execution timed out 4093 ms 18892 KB Time limit exceeded
17 Halted 0 ms 0 KB -