Submission #889452

#	Time	Username	Problem	Language	Result	Execution time	Memory
889452		Denkata	Evacuation plan (IZhO18_plan)	C++14	0 / 100	4054 ms	17468 KiB

plan

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 1e5+3;
int i,j,p,q,n,m,k,raz[maxn],Q;
struct Put
{
    int v,d;
};
bool operator<(Put a,Put b)
{
    return a.d>b.d;
}
priority_queue <Put> pq;
vector <Put> v[maxn];
int par[maxn],sz[maxn];
map <int,int> nomer;
vector <int> stoinosti;
vector <int> group[maxn];
int tek;
struct roll_back
{
    int a,para;
    int b,parb;
    int szb;
    int where;
};
stack <roll_back> s;
struct Zaqvka
{
    int l,r,id;
};
vector <Zaqvka> queries;
int ans[maxn];
void roll_back(int pos)
{
    while(!s.empty() && s.top().where<=pos)
    {
        auto t = s.top();
        s.pop();
        par[t.a] = t.para;
        par[t.b] = t.parb;
        sz[t.para]-=t.szb;
    }
}
int Find(int p)
{
    if(par[p]==p)
        return p;
    return Find(par[p]);
}
void Union(int p,int q,int where)
{
  //  cout<<"Union "<<p<<" "<<q<<" "<<where<<endl;
    int parp,parq;
    parp = Find(p);
    parq = Find(q);
    if(parp==parq)return ;
    if(sz[parp]<sz[parq])swap(p,q);
    s.push({p,parp,q,parq,sz[parq],where});
    par[parq] = parp;
    sz[parp]+=sz[parq];
}
void solve(int l,int r,vector <int> &active)
{
    if(r<l)return ;
    if(active.empty())return ;
   // cout<<l<<" "<<r<<endl;
    if(l==r)
    {
        for(auto j:active)
            ans[queries[j].id] = l;
        return ;
    }
    int mid = (l+r)/2;
    ///jumping through values
    if(tek>mid)
    {
        for(i=tek-1;i>=mid;i--)
        {
            for(auto j:group[i])
            {
                for(auto k:v[j])
                {
                    int pp = k.v;
                    if(raz[pp]>=mid)Union(k.v,j,i);
                }
            }
        }
    }
    else if(tek<mid)
        roll_back(mid-1);
    //cout<<"tuk"<<endl;
    tek = mid;
    vector <int> left;
    vector <int> 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,left);
    solve(mid+1,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,sz[i] = 1;
    int cool;
    cin>>cool;
    while(cool--)
    {
        cin>>p;
        pq.push({p,0});
    }
    for(i=1;i<=n;i++)
        raz[i] = -1;
    int mn = INT_MAX;
    int mx = INT_MIN;
    int cnt;
    while(!pq.empty())
    {
        auto t = pq.top();
        pq.pop();
        if(raz[t.v]==-1)
        {
            raz[t.v] = t.d;
            mx = max(mx,raz[t.v]);
            mn = min(mn,raz[t.v]);
            if(!nomer[raz[t.v]])
            {
                nomer[raz[t.v]]=cnt;cnt++;
                stoinosti.push_back(raz[t.v]);
            }
            group[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});
            }
        }
    }
    /**
    for(i=1;i<=n;i++)
        cout<<r[i]<<" ";
    */
    tek = mx;
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        cin>>p>>q;
        queries.push_back({p,q,i-1});
    }
    vector <int> nach;
    for(i=0;i<Q;i++)
        nach.push_back(i);
    solve(mn,mx,nach);
    for(i=0;i<Q;i++)
        cout<<ans[i]-1<<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 'int main()':
plan.cpp:157:32: warning: 'cnt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |                 nomer[raz[t.v]]=cnt;cnt++;

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