Submission #343356

#	Time	Username	Problem	Language	Result	Execution time	Memory
343356		Traduttore	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1274 ms	105684 KiB

plan

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define F first
#define S second
#define ull unsigned long long
#define ld long double
#define endl '\n'
#define ll long long
#define TIME 1.0*clock()/CLOCKS_PER_SEC
#define pii pair < int32_t , int32_t >
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pll pair <ll,ll>


using namespace std;
using namespace __gnu_pbds;

const int32_t N = 2e5 + 23;
const int rx[] = {-1, +1, 0, 0};
const int ry[] = {0, 0, -1, +1};
typedef tree <int,null_type,less <int>,rb_tree_tag,tree_order_statistics_node_update> orduk;
typedef tree <pair <int,pll>,null_type,less <pair <int,pll> >,rb_tree_tag,tree_order_statistics_node_update> orduk2;
mt19937_64 gen(time(NULL));
ll n,m;
vector <pll> gr[(int)(1e6)];
vector <ll> a;
vector <ll> answers((int)(1e6));
vector <set <ll> > events;
void init() {
    cin>>n>>m;
    for (int i = 0;i < m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        --x;
        --y;
        gr[x].pb({y,z});
        gr[y].pb({x,z});
    }
}
ll ans = 0;
void output() {
cout<<ans<<'\n';
}
struct dsu {
ll parent[(int)(1e6) + 1];
ll rangus[(int)(1e6) + 1];
void make_set (ll v)
{
    parent[v] = v;
    rangus[v] = 0;
}
ll find_set (ll v)
{
    if (v == parent[v]) return v;
    else return parent[v] = find_set(parent[v]);
}
void unite_sets (ll a,ll b,ll curv)
{
    if (a == b) return;
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (events[a].size() < events[b].size()) swap(a,b);
   // cerr<<events[a].size()<<" "<<events[b].size()<<" "<<curv<<'\n';
    for (auto to:events[b]) {
        if (events[a].count(to)) {
              //  cerr<<"WOZ"<<" "<<to<<'\n';
            answers[to] = curv;
       // cerr<<"WOZ"<<'\n';
            events[a].erase(events[a].find(to));
           // cerr<<"WOZ"<<'\n';
        }
        else events[a].insert(to);
    }
    events[b].clear();
    parent[b] = a;
    if (rangus[a] == rangus[b]) ++rangus[a];
}
};
dsu t;
void solve() {
    vector <ll> dist(n, 2e18);
    ll v;
    cin>>v;
    for (int i = 0;i < v;i++)
    {
        int x;
        cin>>x;
        --x;
        dist[x] = 0;
        queue <ll> q;
        q.push(x);
        while (!q.empty()) {
            ll v = q.front();
            q.pop();
            for (auto to:gr[v])
            if (to.S + dist[v] < dist[to.F]) {
                dist[to.F] = to.S + dist[v];
                q.push(to.F);
            }
        }
    }
    vector <pll> dists(n);
    for (int i = 0;i < n;i++)
    {
        dists[i].F = dist[i];
        dists[i].S = i;
    }
    sort(dists.rbegin(),dists.rend());
    vector <int> pos(n);
    for (int i = 0;i < n;i++)
        pos[dists[i].S] = i;
    int qb;
    cin>>qb;
    events.resize(n);
    int yac = 0;
    vector <int> distan(n, -1);
    vector <pll> zapr;
    vector <pll> cow;
    vector <ll> op(n);
    int oper = 0;
    while (qb--)
    {
        int x,y;
        cin>>x>>y;
        --x;
        --y;
        events[x].insert(oper);
        events[y].insert(oper);
        cow.pb({x,y});
        /*if (n > 5e3 && q != 1) {
            ans = min(dist[x],dist[y]);
            output();
            continue;
        }*/
        ++oper;
    }
    for (int i = 0;i < n;i++)
        t.make_set(i);
    vector <pair <ll,pll> > nenj;
    for (int i = 0;i < n;i++)
    {
        for (auto to:gr[i])
        nenj.pb({min(dist[to.F],dist[i]),{to.F,i}});
    }
    sort(nenj.rbegin(),nenj.rend());
    for (auto to:nenj)
        {
           // cerr<<to.F<<" "<<to.S.F<<" "<<to.S.S<<" "<<"WOW"<<'\n';
            t.unite_sets(to.S.F,to.S.S,to.F);
        }
    for (int i = 0;i < cow.size();i++)
    {
        ans = answers[i];
        output();
    }
}
int32_t main() {
    IOS;
    srand(time(0));
    int32_t m;
    m = 10;
    m-=9;
    while (m--)
    {
        init();
        solve();
    }
    return 0;
}
/*9 5 1*/
/*9 5 1 8 3*/

Compilation message (stderr)

plan.cpp: In function 'void solve()':
plan.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0;i < cow.size();i++)
      |                    ~~^~~~~~~~~~~~
plan.cpp:121:9: warning: unused variable 'yac' [-Wunused-variable]
  121 |     int yac = 0;
      |         ^~~

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