Submission #890711

#	Time	Username	Problem	Language	Result	Execution time	Memory
890711		Denkata	Evacuation plan (IZhO18_plan)	C++14	100 / 100	441 ms	82532 KiB

plan

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 1e5+3;
long long i,j,p,q,n,m,k,raz[maxn],Q;
struct Put
{
    long long v,d;
};
bool operator<(Put a,Put b)
{
    return a.d>b.d;
}
priority_queue <Put> pq;
vector <Put> v[maxn];
map <long long,bool> povtorki;
long long par[maxn],rnk[maxn];
vector <long long> stoinosti;
vector <pair<long long,long long>> group[maxn];
long long tek;
struct roll_back
{
    long long a;
    long long b;
    long long rnka,rnkb;
    long long where;
};
stack <roll_back> s;
struct Zaqvka
{
    long long l,r,id;
};
vector <Zaqvka> queries;
long long ans[maxn];
void roll_back(long long pos)
{
    while(!s.empty() && s.top().where<=pos)
    {
        auto t = s.top();
        s.pop();
        rnk[t.a] = t.rnka;
        rnk[t.b] = t.rnkb;
        par[t.a] = t.a;
        par[t.b] = t.b;
    }
}
long long Find(long long p)
{
    if(par[p]==p)
        return p;
    return Find(par[p]);
}
void Union(long long p,long long q,long long where)
{
  //  cout<<"Union "<<p<<" "<<q<<" "<<where<<endl;
    long long parp,parq;
    p = Find(p);
    q = Find(q);
    if(p==q)return ;
    //cout<<"svurzvame "<<p<<" "<<q<<endl;
    s.push({p,q,rnk[p],rnk[q],where});
    if(rnk[p]<rnk[q])swap(p,q);
    if(rnk[p]==rnk[q])
        rnk[p]++;
    par[q] = p;
}
void solve(long long l,long long r,vector <long long> &active)
{
    if(r<l)return ;
    if(active.empty())return ;
    if(l==r)
    {
        for(auto j:active)
            ans[queries[j].id] = stoinosti[l];
        return ;
    }
    long long mid = (l+r+1)/2;
    ///jumping through values
    if(tek>mid)
    {
        for(i=tek-1;i>=mid;i--)
        {
            for(auto j:group[i])
            {
                Union(j.first,j.second,i);
            }
        }
    }
    roll_back(mid-1);
    //cout<<"tuk"<<endl;
    tek = mid;
    vector <long long> left;
    vector <long long> right;
    for(auto i:active)
    {
     //   cout<<i<<" is active"<<endl;
        p = queries[i].l;
        q = queries[i].r;
    //    cout<<p<<" pq "<<q<<endl;
        if(Find(p)==Find(q))
            right.push_back(i);
        else left.push_back(i);
    }
    active.clear();

    /**
    cout<<"left "<<endl;
    for(auto i:left)
        cout<<i<<endl;

    cout<<"right"<<endl;
    for(auto i:right)
        cout<<i<<endl;
    */
    solve(l,mid-1,left);
    solve(mid,r,right);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>p>>q>>j;
        v[p].push_back({q,j});
        v[q].push_back({p,j});
    }
    for(i=1;i<=n;i++)
        par[i] = i,rnk[i] = 1;
    long long cool;
    cin>>cool;
    while(cool--)
    {
        cin>>p;
        pq.push({p,0});
    }
    for(i=1;i<=n;i++)
        raz[i] = -1;
    long long cnt;
    while(!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        if(raz[t.v]==-1)
        {
            raz[t.v] = t.d;
            if(!povtorki[raz[t.v]])
                stoinosti.push_back(raz[t.v]),povtorki[raz[t.v]] = true;
            //group[nomer[raz[t.v]]].push_back(t.v);
            for(auto i:v[t.v])
            {
                if(raz[i.v]==-1)
                    pq.push({i.v,t.d+i.d});
            }
        }
    }
    sort(stoinosti.begin(),stoinosti.end());

    for(i=1;i<=n;i++)
    {
        p = lower_bound(stoinosti.begin(),stoinosti.end(),raz[i])-stoinosti.begin();
        // cout<<i<<" grupa "<<p<<" "<<stoinosti[p]<<endl;
        for(auto j:v[i])
        {
            long long h = min(raz[i],raz[j.v]);
            p = lower_bound(stoinosti.begin(),stoinosti.end(),h)-stoinosti.begin();
          //  cout<<i<<" "<<j.v<<" "<<h<<endl;
            group[p].push_back({i,j.v});
        }
    }
    /**
    for(i=1;i<=n;i++)
        cout<<r[i]<<" ";
    */
    tek = stoinosti.size();
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        cin>>p>>q;
        queries.push_back({p,q,i-1});
    }
    vector <long long> nach;
    for(i=0;i<Q;i++)
        nach.push_back(i);
    solve(0,stoinosti.size()-1,nach);
    for(i=0;i<Q;i++)
        cout<<ans[i]<<endl;
    cout<<endl;
    return 0;
}
/**
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7  10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Compilation message (stderr)

plan.cpp: In function 'void Union(long long int, long long int, long long int)':
plan.cpp:56:15: warning: unused variable 'parp' [-Wunused-variable]
   56 |     long long parp,parq;
      |               ^~~~
plan.cpp:56:20: warning: unused variable 'parq' [-Wunused-variable]
   56 |     long long parp,parq;
      |                    ^~~~
plan.cpp: In function 'int main()':
plan.cpp:141:15: warning: unused variable 'cnt' [-Wunused-variable]
  141 |     long long cnt;
      |               ^~~

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