Submission #519787

#	Time	Username	Problem	Language	Result	Execution time	Memory
519787		Dasha_Gnedko	Evacuation plan (IZhO18_plan)	C++17	100 / 100	603 ms	80648 KiB

plan

#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(time(0));

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long

const int N = 1e6 + 100;
const int M = 18;
const int mod = 998244353;
const int inf = 1e9 + 7;

vector < pair < int, int > > g[N];
int ra[N], ans[N], pr[N], u[N];
vector < pair < pair < int, int >, int > > ask[N];

int get(int v)
{
    if (pr[v] == v) return v;
    return pr[v] = get(pr[v]);
}

void unite(int a, int b, int mx)
{
    a = get(a); b = get(b);
    if (a == b) return;
    if (sz(ask[a]) < sz(ask[b])) swap(a, b);
    int uk = 0;
    for(int i = 0; i < sz(ask[b]); i++)
    {
        int x = ask[b][i].F.F, y = ask[b][i].F.S, numb = ask[b][i].S;
        x = get(x); y = get(y);
        if (x == y) continue;
        if (x != a) swap(x, y);
        if (x != a)
        {
            ask[a].pb(ask[b][i]);
            continue;
        }
        ans[numb] = mx;
    }
    ask[b].clear();
    pr[b] = a;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL

    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;
        g[x].pb({y, z});
        g[y].pb({x, z});
    }
    for(int i = 0; i < n; i++)
        ra[i] = inf;
    priority_queue < pair < int, int > > q;
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        x--;
        q.push({0, x});
        ra[x] = 0;
    }
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        ask[x].pb({{x, y}, i});
        ask[y].pb({{x, y}, i});
    }
    for(int i = 0; i < n; i++)
        pr[i] = i;
    while (!q.empty())
    {
        int r = -q.top().F, v = q.top().S;
        q.pop();
        for(auto to: g[v])
        {
            if (ra[to.F] > ra[v] + to.S)
            {
                ra[to.F] = ra[v] + to.S;
                q.push({-ra[to.F], to.F});
            }
        }
    }
    vector < pair < int, int > > a;
    for(int i = 0; i < n; i++)
        a.pb({ra[i], i});
    sort(a.rbegin(), a.rend());
    for(auto x: a)
    {
        int v = x.S;
        u[v] = 1;
        for(auto to: g[v])
        {
            if (!u[to.F]) continue;
            unite(v, to.F, x.F);
        }
    }
    for(int i = 0; i < Q; i++)
        cout << ans[i] << endl;
}

Compilation message (stderr)

plan.cpp: In function 'void unite(int, int, int)':
plan.cpp:48:9: warning: unused variable 'uk' [-Wunused-variable]
   48 |     int uk = 0;
      |         ^~
plan.cpp: In function 'int32_t main()':
plan.cpp:116:13: warning: unused variable 'r' [-Wunused-variable]
  116 |         int r = -q.top().F, v = q.top().S;
      |             ^

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46