Submission #343328

#	Time	Username	Problem	Language	Result	Execution time	Memory
343328		Traduttore	Evacuation plan (IZhO18_plan)	C++17	54 / 100	4051 ms	60784 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;
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)
{
    if (a == b) return;
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (rangus[a] < rangus[b]) swap(a,b);
    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;
    int yac = 0;
    vector <int> distan(n, -1);
    vector <pll> zapr;
    vector <pll> cow;
    vector <ll> answers;
    vector <ll> op(n);
    answers.resize(qb);
    while (qb--)
    {
        int x,y;
        cin>>x>>y;
        --x;
        --y;
        zapr.pb({x,y});
        cow.pb({max(pos[x],pos[y]),zapr.size()-1});
        /*if (n > 5e3 && q != 1) {
            ans = min(dist[x],dist[y]);
            output();
            continue;
        }*/
    }
    sort(cow.begin(),cow.end());
    orduk wow;
    for (int i = 0;i < n;i++)
        t.make_set(i);
    int ptr = 0;
    int wsz = 0;
    for (int i = 0;i < n;i++)
    {
        for (auto to:gr[dists[i].S])
        if (op[to.F]) t.unite_sets(dists[i].S,to.F);
        op[dists[i].S] = 1;
        for (;ptr < cow.size();ptr++)
        {
            if (cow[ptr].F > i) break;
            wow.insert(cow[ptr].S);
            ++wsz;
        }
        int m = 0;
        while (1)
        {
            if (m >= wsz) break;
            int to = (*wow.find_by_order(m));
            //cout<<dists[i].F<<" "<<dists[i].S<<" "<<zapr[to].F<<" "<<zapr[to].S<<" "<<t.find_set(zapr[to].F)<<" "<<t.find_set(zapr[to].S)<<'\n';
            if (t.find_set(zapr[to].F)==t.find_set(zapr[to].S)) {
                 //   cout<<zapr[to.S].F<<" "<<zapr[to.S].S<<" "<<t.find_set(zapr[to.S].F)<<" "<<t.find_set(zapr[to.S].S)<<'\n';
                answers[to] = dists[i].F;
                wow.erase(wow.find(to));
                --wsz;
            }
            else ++m;
        }
    }
    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:138:19: 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]
  138 |         for (;ptr < cow.size();ptr++)
      |               ~~~~^~~~~~~~~~~~
plan.cpp:159: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]
  159 |     for (int i = 0;i < cow.size();i++)
      |                    ~~^~~~~~~~~~~~
plan.cpp:106:9: warning: unused variable 'yac' [-Wunused-variable]
  106 |     int yac = 0;
      |         ^~~

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