Submission #709819

#	Time	Username	Problem	Language	Result	Execution time	Memory
709819		groshi	Evacuation plan (IZhO18_plan)	C++17	22 / 100	576 ms	73360 KiB

plan

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct wi{
    vector<int> Q;
    int odl=1e9;
}*w;
int ojc[200000];
int pocz[200000];
int kon[200000];
int ostd[200000];
int kraw[200000][2];
int zapp[200000][2];
int find_u(int x)
{
    if(ojc[x]==x)
        return x;
    return ojc[x]=find_u(ojc[x]);
}
void union_f(int x,int y)
{
    //cout<<"lacze "<<x<<" "<<y<<"\n";
    ojc[find_u(x)]=find_u(y);
}
int32_t main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m,x,y,z;
    cin>>n>>m;
    w=new wi[n+3];
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        w[x].Q.push_back(y);
        w[y].Q.push_back(x);
        w[x].Q.push_back(z);
        w[y].Q.push_back(z);
        kraw[i][0]=x;
        kraw[i][1]=y;
    }
    int mam;
    cin>>mam;
    priority_queue<pair<int,int> > kolejka;
    for(int i=1;i<=mam;i++)
    {
        cin>>x;
        kolejka.push({0,x});
    }
    while(!kolejka.empty())
    {
        auto para=kolejka.top();
        kolejka.pop();
        int x=para.second;
        int ile=-para.first;
        if(w[x].odl!=1e9)
            continue;
        w[x].odl=ile;
        for(int i=0;i<w[x].Q.size();i+=2)
        {
            int pom=w[x].Q[i];
            if(w[pom].odl!=1e9)
            continue;
            kolejka.push({-ile-w[x].Q[i+1],pom});
        }
    }
    int zap;
    cin>>zap;
    for(int i=1;i<=zap;i++)
    {
        cin>>x>>y;
        pocz[i]=0,kon[i]=1e9,ostd[i]=-1;
        zapp[i][0]=x;
        zapp[i][1]=y;
    }
    vector<pair<int,pair<int,int> > > krawedzie;
    for(int i=1;i<=m;i++)
    {
        x=kraw[i][0];
        y=kraw[i][1];
        krawedzie.push_back({min(w[x].odl,w[y].odl),{x,y}});
        //cout<<"wrzucam "<<x<<" "<<y<<": "<<w[x].odl<<" "<<w[y].odl<<"\n";
    }
    sort(krawedzie.begin(),krawedzie.end());
    for(int a=0;a<=30;a++)
    {
        //cout<<a<<": ";
        for(int i=1;i<=n;i++)
            ojc[i]=i;
        vector<pair<pair<int,int>,pair<int,int> > > wydarzenia;
        for(int i=1;i<=zap;i++)
            wydarzenia.push_back({{(pocz[i]+kon[i])/2,i},{zapp[i][0],zapp[i][1]}});
        int gdzie=wydarzenia.size()-1;
        sort(wydarzenia.begin(),wydarzenia.end());
        while(gdzie>=0 && wydarzenia[gdzie].first.first>krawedzie.back().first)
        {
            int x=wydarzenia[gdzie].second.first;
            int y=wydarzenia[gdzie].second.second;
            int co=wydarzenia[gdzie].first.second;
            if(find_u(x)!=find_u(y))
            {
                kon[co]=wydarzenia[gdzie].first.first;
                //cout<<"essa "<<co<<" "<<wydarzenia[gdzie].first.first<<" "<<krawedzie.back().first<<"\n";
            }
            else{
                //cout<<"dobrze "<<wydarzenia[gdzie].first.first<<" dla "<<x<<" "<<y<<"\n";
                pocz[co]=wydarzenia[gdzie].first.first+1;
                ostd[co]=wydarzenia[gdzie].first.first;
            }
            gdzie--;
        }
        for(int i=krawedzie.size()-1;i>=0;i--)
        {
            union_f(krawedzie[i].second.first,krawedzie[i].second.second);
            if(i>0 && krawedzie[i].first==krawedzie[i-1].first)
                continue;
            while(gdzie>=0 && (i==0 || wydarzenia[gdzie].first.first>krawedzie[i-1].first))
            {
                int x=wydarzenia[gdzie].second.first;
                int y=wydarzenia[gdzie].second.second;
                int co=wydarzenia[gdzie].first.second;
                if(find_u(x)!=find_u(y))
                    kon[co]=wydarzenia[gdzie].first.first;
                else{
                    //cout<<"dobrze "<<wydarzenia[gdzie].first.first<<" dla "<<x<<" "<<y<<"\n";
                    pocz[co]=wydarzenia[gdzie].first.first+1;
                    ostd[co]=wydarzenia[gdzie].first.first;
                }
                gdzie--;
            }
        }
    }
    for(int i=1;i<=zap;i++)
        cout<<ostd[i]<<"\n";
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int32_t main()':
plan.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i=0;i<w[x].Q.size();i+=2)
      |                     ~^~~~~~~~~~~~~~

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