oj.uz

Submission #894646

# Submission time Handle Problem Language Result Execution time Memory
894646 2023-12-28T15:20:57 Z CyberCow Evacuation plan (IZhO18_plan) C++17
19 / 100
 257 ms 32712 KB 
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);

const int N = 100005;

vector<pair<int, int>> v[N];
int dist[N];

int p[N], sz[N];
int mecpapa;
int has[N];
int gggg[N];

void make_set(int i)
{
    p[i] = i;
    sz[i] = 1;
    gggg[i] = dist[i];
}

int get_papa(int i)
{
    if (p[i] == i)
        return i;
    return get_papa(p[i]);
}

vector<int> mde[N];


void union_set(int a, int b, int ggg)
{
    a = get_papa(a);
    b = get_papa(b);
    if (a == b) return;
    if (sz[a] < sz[b])
        swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
    mde[a].push_back(b);
    has[b] = a;
    gggg[b] = ggg;
    mecpapa = a;
}


int xorutyun[N];

void Dfs(int g, int xr)
{
    xorutyun[g] = xr;
    for (auto to : mde[g])
    {
        Dfs(to, xr + 1);
    }
}

void solve()
{
    int n, i, j, m, x, y, w;
    cin >> n >> m;
    for ( i = 0; i < m; i++)
    {
        cin >> x >> y >> w;
        v[x].push_back({ y, w });
        v[y].push_back({ x, w });
    }
    for ( i = 1; i <= n; i++)
    {
        dist[i] = 1e9;
    }
    int k;
    cin >> k;
    priority_queue<pair<int, int>> q;
    for ( i = 0; i < k; i++)
    {
        cin >> x;
        q.push({ 0, x });
        dist[x] = 0;
    }
    while (!q.empty())
    {
        pair<int, int> gag = q.top();
        q.pop();
        gag.first *= -1;
        if (gag.first > dist[gag.second])
            continue;
        for (auto to : v[gag.second])
        {
            if (gag.first + to.second < dist[to.first])
            {
                dist[to.first] = gag.first + to.second;
                q.push({-dist[to.first], to.first });
            }
        }
    }
    vector<pair<int, int>> hert;
    for ( i = 1; i <= n; i++)
    {
        hert.push_back({ dist[i], i });
        make_set(i);
    }
    sort(hert.begin(), hert.end());
    for ( i = hert.size() - 1; i >= 0; i--)
    {
        for (auto to : v[hert[i].second])
        {
            if (dist[to.first] >= hert[i].first)
            {
                union_set(to.first, hert[i].second, hert[i].first);
            }
        }
    }
    Dfs(mecpapa, 0);
    int qq;
    cin >> qq;
    for ( i = 0; i < qq; i++)
    {
        cin >> x >> y;
        int res = 1e9;
        while (x != y)
        {
            if (xorutyun[x] > xorutyun[y])
            {
                res = min(res, gggg[x]);
                x = has[x];
            }
            else
            {
                res = min(res, gggg[y]);
                y = has[y];
            }
        }
        res = min(res, gggg[x]);
        cout << res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message

plan.cpp: In function 'void solve()':
plan.cpp:84:15: warning: unused variable 'j' [-Wunused-variable]
   84 |     int n, i, j, m, x, y, w;
      |               ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Incorrect 1 ms 7260 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Incorrect 1 ms 7260 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 15952 KB Output is correct
2 Correct 249 ms 32224 KB Output is correct
3 Correct 247 ms 32272 KB Output is correct
4 Correct 44 ms 13788 KB Output is correct
5 Correct 257 ms 32064 KB Output is correct
6 Correct 243 ms 32172 KB Output is correct
7 Correct 229 ms 32288 KB Output is correct
8 Correct 257 ms 32072 KB Output is correct
9 Correct 234 ms 32080 KB Output is correct
10 Correct 217 ms 32240 KB Output is correct
11 Correct 247 ms 32372 KB Output is correct
12 Correct 216 ms 32240 KB Output is correct
13 Correct 236 ms 32044 KB Output is correct
14 Correct 216 ms 32188 KB Output is correct
15 Correct 216 ms 32712 KB Output is correct
16 Correct 213 ms 32076 KB Output is correct
17 Correct 227 ms 32276 KB Output is correct
18 Correct 222 ms 32120 KB Output is correct
19 Correct 41 ms 13768 KB Output is correct
20 Correct 240 ms 32580 KB Output is correct
21 Correct 209 ms 32196 KB Output is correct
22 Correct 59 ms 15404 KB Output is correct
23 Correct 79 ms 14360 KB Output is correct
24 Correct 58 ms 15564 KB Output is correct
25 Correct 55 ms 15308 KB Output is correct
26 Correct 65 ms 14432 KB Output is correct
27 Correct 44 ms 13768 KB Output is correct
28 Correct 59 ms 15520 KB Output is correct
29 Correct 40 ms 13512 KB Output is correct
30 Correct 58 ms 15348 KB Output is correct
31 Correct 39 ms 13508 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 1 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7512 KB Output is correct
7 Incorrect 1 ms 7260 KB Output isn't correct
8 Halted 0 ms 0 KB -