oj.uz

답안 #893981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
893981 2023-12-27T18:16:17 Z borisAngelov Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 39252 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;

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

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

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

        return root(par[node]);
    }

    inline 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];
        }
    }

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

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

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

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

    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:241: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]
  241 |         for (int i = 0; i < g[node].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~
plan.cpp:258: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]
  258 |         for (int j = 0; j < g[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7524 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 3 ms 7604 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 7512 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 7648 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 5 ms 7672 KB Output is correct
15 Correct 5 ms 7528 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7524 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 3 ms 7604 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 7512 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 7648 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 5 ms 7672 KB Output is correct
15 Correct 5 ms 7528 KB Output is correct
16 Correct 3236 ms 19188 KB Output is correct
17 Correct 2338 ms 38916 KB Output is correct
18 Correct 210 ms 10896 KB Output is correct
19 Correct 75 ms 23868 KB Output is correct
20 Correct 2483 ms 39252 KB Output is correct
21 Correct 305 ms 27204 KB Output is correct
22 Execution timed out 4070 ms 20432 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 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 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 20028 KB Output is correct
2 Correct 290 ms 34908 KB Output is correct
3 Correct 283 ms 34740 KB Output is correct
4 Correct 90 ms 17612 KB Output is correct
5 Correct 335 ms 35152 KB Output is correct
6 Correct 302 ms 33944 KB Output is correct
7 Correct 326 ms 35196 KB Output is correct
8 Correct 262 ms 34184 KB Output is correct
9 Correct 303 ms 33920 KB Output is correct
10 Correct 287 ms 34972 KB Output is correct
11 Correct 339 ms 34672 KB Output is correct
12 Correct 283 ms 35216 KB Output is correct
13 Correct 291 ms 34644 KB Output is correct
14 Correct 278 ms 34440 KB Output is correct
15 Correct 316 ms 35880 KB Output is correct
16 Correct 277 ms 34764 KB Output is correct
17 Correct 275 ms 33972 KB Output is correct
18 Correct 312 ms 34092 KB Output is correct
19 Correct 98 ms 17576 KB Output is correct
20 Correct 292 ms 34636 KB Output is correct
21 Correct 230 ms 33316 KB Output is correct
22 Correct 52 ms 16708 KB Output is correct
23 Correct 121 ms 16640 KB Output is correct
24 Correct 50 ms 16708 KB Output is correct
25 Correct 70 ms 16696 KB Output is correct
26 Correct 99 ms 16336 KB Output is correct
27 Correct 99 ms 17556 KB Output is correct
28 Correct 56 ms 16592 KB Output is correct
29 Correct 88 ms 17620 KB Output is correct
30 Correct 52 ms 16708 KB Output is correct
31 Correct 97 ms 17616 KB Output is correct

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7516 KB Output is correct
2 Correct 2 ms 7524 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 3 ms 7604 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 7512 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 7648 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 5 ms 7672 KB Output is correct
15 Correct 5 ms 7528 KB Output is correct
16 Correct 3236 ms 19188 KB Output is correct
17 Correct 2338 ms 38916 KB Output is correct
18 Correct 210 ms 10896 KB Output is correct
19 Correct 75 ms 23868 KB Output is correct
20 Correct 2483 ms 39252 KB Output is correct
21 Correct 305 ms 27204 KB Output is correct
22 Execution timed out 4070 ms 20432 KB Time limit exceeded
23 Halted 0 ms 0 KB -