oj.uz

Submission #894637

# Submission time Handle Problem Language Result Execution time Memory
894637 2023-12-28T14:49:27 Z CyberCow Evacuation plan (IZhO18_plan) C++17
23 / 100
 297 ms 34140 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[a] = gggg[b];
    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());
    int anc = -1;
    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, dist[x]);
                x = has[x];
            }
            else
            {
                res = min(res, dist[y]);
                y = has[y];
            }
        }
        res = min(res, dist[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;
      |               ^
plan.cpp:128:9: warning: unused variable 'anc' [-Wunused-variable]
  128 |     int anc = -1;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 2 ms 7512 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 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7300 KB Output is correct
15 Correct 2 ms 7344 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 2 ms 7512 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 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7300 KB Output is correct
15 Correct 2 ms 7344 KB Output is correct
16 Correct 81 ms 15548 KB Output is correct
17 Correct 297 ms 33924 KB Output is correct
18 Correct 19 ms 9560 KB Output is correct
19 Correct 71 ms 17088 KB Output is correct
20 Correct 256 ms 33856 KB Output is correct
21 Correct 155 ms 20556 KB Output is correct
22 Correct 65 ms 16072 KB Output is correct
23 Correct 254 ms 33800 KB Output is correct
24 Correct 293 ms 33860 KB Output is correct
25 Correct 244 ms 34140 KB Output is correct
26 Correct 72 ms 16988 KB Output is correct
27 Correct 70 ms 17080 KB Output is correct
28 Correct 72 ms 16836 KB Output is correct
29 Correct 83 ms 16928 KB Output is correct
30 Correct 71 ms 17096 KB Output is correct

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
0 / 19.0

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

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 2 ms 7512 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 7260 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 7260 KB Output is correct
9 Correct 2 ms 7260 KB Output is correct
10 Correct 2 ms 7260 KB Output is correct
11 Correct 2 ms 7260 KB Output is correct
12 Correct 2 ms 7260 KB Output is correct
13 Correct 2 ms 7260 KB Output is correct
14 Correct 2 ms 7300 KB Output is correct
15 Correct 2 ms 7344 KB Output is correct
16 Correct 81 ms 15548 KB Output is correct
17 Correct 297 ms 33924 KB Output is correct
18 Correct 19 ms 9560 KB Output is correct
19 Correct 71 ms 17088 KB Output is correct
20 Correct 256 ms 33856 KB Output is correct
21 Correct 155 ms 20556 KB Output is correct
22 Correct 65 ms 16072 KB Output is correct
23 Correct 254 ms 33800 KB Output is correct
24 Correct 293 ms 33860 KB Output is correct
25 Correct 244 ms 34140 KB Output is correct
26 Correct 72 ms 16988 KB Output is correct
27 Correct 70 ms 17080 KB Output is correct
28 Correct 72 ms 16836 KB Output is correct
29 Correct 83 ms 16928 KB Output is correct
30 Correct 71 ms 17096 KB Output is correct
31 Incorrect 2 ms 7260 KB Output isn't correct
32 Halted 0 ms 0 KB -