oj.uz

답안 #893987

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

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

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

    dsu.init();

    vector<int> starting;

    for (int i = 0; i < q; ++i)
    {
        starting.push_back(i);
    }

    if (clock() / CLOCKS_PER_SEC > 0.1)
    {
        return 1;
    }

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

    for (int i = 0; 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 7256 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7672 KB Output is correct
6 Correct 2 ms 7604 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 7648 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 2 ms 7584 KB Output is correct
13 Correct 4 ms 7512 KB Output is correct
14 Correct 7 ms 7712 KB Output is correct
15 Correct 5 ms 7648 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7672 KB Output is correct
6 Correct 2 ms 7604 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 7648 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 2 ms 7584 KB Output is correct
13 Correct 4 ms 7512 KB Output is correct
14 Correct 7 ms 7712 KB Output is correct
15 Correct 5 ms 7648 KB Output is correct
16 Correct 3193 ms 17352 KB Output is correct
17 Correct 2264 ms 34048 KB Output is correct
18 Correct 208 ms 9952 KB Output is correct
19 Correct 91 ms 22100 KB Output is correct
20 Correct 2397 ms 34388 KB Output is correct
21 Correct 302 ms 23744 KB Output is correct
22 Execution timed out 4038 ms 18636 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7512 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 1 ms 7256 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 124 ms 17936 KB Output is correct
2 Correct 288 ms 30428 KB Output is correct
3 Correct 300 ms 30336 KB Output is correct
4 Correct 96 ms 16460 KB Output is correct
5 Correct 274 ms 30916 KB Output is correct
6 Correct 281 ms 29568 KB Output is correct
7 Correct 268 ms 30396 KB Output is correct
8 Correct 318 ms 29656 KB Output is correct
9 Correct 255 ms 29712 KB Output is correct
10 Correct 292 ms 30612 KB Output is correct
11 Correct 294 ms 30404 KB Output is correct
12 Correct 325 ms 31084 KB Output is correct
13 Correct 276 ms 30264 KB Output is correct
14 Correct 289 ms 29724 KB Output is correct
15 Correct 290 ms 30768 KB Output is correct
16 Correct 335 ms 30392 KB Output is correct
17 Correct 266 ms 29636 KB Output is correct
18 Correct 281 ms 29664 KB Output is correct
19 Correct 77 ms 16340 KB Output is correct
20 Correct 263 ms 30412 KB Output is correct
21 Correct 204 ms 28812 KB Output is correct
22 Correct 49 ms 15428 KB Output is correct
23 Correct 120 ms 15356 KB Output is correct
24 Correct 48 ms 15176 KB Output is correct
25 Correct 48 ms 15324 KB Output is correct
26 Correct 103 ms 15116 KB Output is correct
27 Correct 86 ms 16440 KB Output is correct
28 Correct 49 ms 15424 KB Output is correct
29 Correct 88 ms 16388 KB Output is correct
30 Correct 49 ms 15424 KB Output is correct
31 Correct 90 ms 16336 KB Output is correct

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 3 ms 7512 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 3 ms 7672 KB Output is correct
6 Correct 2 ms 7604 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 7648 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 2 ms 7584 KB Output is correct
13 Correct 4 ms 7512 KB Output is correct
14 Correct 7 ms 7712 KB Output is correct
15 Correct 5 ms 7648 KB Output is correct
16 Correct 3193 ms 17352 KB Output is correct
17 Correct 2264 ms 34048 KB Output is correct
18 Correct 208 ms 9952 KB Output is correct
19 Correct 91 ms 22100 KB Output is correct
20 Correct 2397 ms 34388 KB Output is correct
21 Correct 302 ms 23744 KB Output is correct
22 Execution timed out 4038 ms 18636 KB Time limit exceeded
23 Halted 0 ms 0 KB -