oj.uz

Submission #893979

# Submission time Handle Problem Language Result Execution time Memory
893979 2023-12-27T18:10:58 Z borisAngelov Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 36792 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));
        }
    }

    if (clock() / CLOCKS_PER_SEC != 0.0)
    {
        return 1;
    }

    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 2 ms 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7256 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 7 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 7 ms 7516 KB Output is correct
15 Correct 9 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 2 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7256 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 7 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 7 ms 7516 KB Output is correct
15 Correct 9 ms 7516 KB Output is correct
16 Execution timed out 4019 ms 18552 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 7260 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7260 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 1 ms 7516 KB Output is correct
8 Correct 2 ms 7512 KB Output is correct
9 Correct 2 ms 7460 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 172 ms 21520 KB Output is correct
2 Correct 411 ms 36040 KB Output is correct
3 Correct 380 ms 35820 KB Output is correct
4 Correct 106 ms 16172 KB Output is correct
5 Correct 399 ms 36288 KB Output is correct
6 Correct 369 ms 35420 KB Output is correct
7 Correct 407 ms 35188 KB Output is correct
8 Correct 492 ms 35524 KB Output is correct
9 Correct 365 ms 35776 KB Output is correct
10 Correct 388 ms 36180 KB Output is correct
11 Correct 407 ms 36188 KB Output is correct
12 Correct 380 ms 36004 KB Output is correct
13 Correct 401 ms 35932 KB Output is correct
14 Correct 338 ms 35360 KB Output is correct
15 Correct 451 ms 36792 KB Output is correct
16 Correct 364 ms 35780 KB Output is correct
17 Correct 346 ms 35520 KB Output is correct
18 Correct 363 ms 35256 KB Output is correct
19 Correct 82 ms 15128 KB Output is correct
20 Correct 377 ms 35896 KB Output is correct
21 Correct 230 ms 34308 KB Output is correct
22 Correct 69 ms 17356 KB Output is correct
23 Correct 151 ms 16412 KB Output is correct
24 Correct 58 ms 17220 KB Output is correct
25 Correct 54 ms 17216 KB Output is correct
26 Correct 154 ms 16968 KB Output is correct
27 Correct 91 ms 16072 KB Output is correct
28 Correct 62 ms 17324 KB Output is correct
29 Correct 95 ms 16064 KB Output is correct
30 Correct 54 ms 17216 KB Output is correct
31 Correct 99 ms 16360 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 2 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7256 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 7 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 7 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 7 ms 7516 KB Output is correct
15 Correct 9 ms 7516 KB Output is correct
16 Execution timed out 4019 ms 18552 KB Time limit exceeded
17 Halted 0 ms 0 KB -