Submission #1230176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230176		vivkostov	Wild Boar (JOI18_wild_boar)	C++20	62 / 100	1554 ms	396580 KiB

wild_boar

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const long long int inf=1e18;
struct cell
{
    long long int from,to,st;
    bool operator<(const cell&a)const
    {
        return st>a.st;
    }
};
struct query
{
    long long int ind,st;
};
bool cmp(query a1,query a2)
{
    return a1.st<a2.st;
}
long long int n,m,t,k,b[200005];
cell a[2005];
query c[2005];
vector<cell>v[2005];
long long int used1[6005][2005],par1[6005][2005],used2[6005][2005],par2[6005][2005],ind[2005][2005],lamp[2005];
void dijkstra(long long int beg,long long int from,long long int ind)
{
    cell w,nb;
    w.from=from;
    w.to=beg;
    w.st=0;
    priority_queue<cell>q;
    q.push(w);
    memset(lamp,0,sizeof(lamp));
    long long int st;

    while(q.size())
    {
        w=q.top();
        q.pop();
        //cout<<w.from<<" "<<w.to<<" "<<used1[ind][w.to]<<" "<<used2[ind][w.to]<<endl;
        if(lamp[w.to]==2)continue;
        if(lamp[w.to]==0&&w.st!=used1[ind][w.to])continue;
        if(lamp[w.to]==1&&w.st!=used2[ind][w.to])continue;
        lamp[w.to]++;
        for(long long int i=0;i<v[w.to].size();i++)
        {
            nb=v[w.to][i];
            if(lamp[w.to]==1)
            {
                st=used1[ind][w.to]+v[w.to][i].st;
            }
            else
            {
                st=used2[ind][w.to]+v[w.to][i].st;
            }
            if(nb.to==w.from)continue;
            //cout<<st<<" "<<nb.to<<endl;
            nb.st=st;
            if(used1[ind][nb.to]>st||!used1[ind][nb.to])
            {
                //cout<<nb.to<<" !1"<<endl;
                q.push(nb);
                if(w.to!=par1[ind][nb.to])
                {
                    used2[ind][nb.to]=used1[ind][nb.to];
                    par2[ind][nb.to]=par1[ind][nb.to];
                }
                used1[ind][nb.to]=st;
                par1[ind][nb.to]=w.to;
            }
            else if(used2[ind][nb.to]>st||!used2[ind][nb.to])
            {
                //cout<<nb.to<<" !2"<<endl;
                if(w.to!=par1[ind][nb.to])
                {
                    q.push(nb);
                    used2[ind][nb.to]=st;
                    par2[ind][nb.to]=w.to;
                }
            }
        }
    }
}
void prec()
{
    long long int br=0;
    for(long long int i=1;i<=n;i++)
    {
        br++;
        ind[i][0]=br;
        dijkstra(i,0,br);
    }
    for(long long int i=1;i<=m;i++)
    {
        br++;
        ind[a[i].to][a[i].from]=br;
        dijkstra(a[i].to,a[i].from,br);
        br++;
        ind[a[i].from][a[i].to]=br;
        dijkstra(a[i].from,a[i].to,br);
    }
    /*
    for(long long int i=1;i<=n;i++)
    {
        for(long long int j=0;j<=n;j++)
        {
            br=ind[i][j];
            cout<<i<<" "<<j<<" | ";
            for(long long int z=1;z<=n;z++)
            {
                cout<<used1[br][z]<<" ";
            }
            cout<<endl;
        }
    }
    */
}
query mi[10];
void resh()
{
    long long int ot1=0,ot2=0,p1=0,p2=0,in;
    for(long long int i=1;i<k;i++)
    {
        if(i==1)
        {
            in=ind[b[i]][0];
            ot1=used1[in][b[i+1]];
            ot2=used2[in][b[i+1]];
            p1=par1[in][b[i+1]];
            p2=par2[in][b[i+1]];
            //cout<<ot1<<" "<<ot2<<" "<<p1<<" "<<p2<<endl;
            continue;
        }
        in=ind[b[i]][p1];
        if(used1[in][b[i+1]]==0)
        {
            cout<<-1<<endl;
            return;
        }
        mi[1].st=ot1+used1[in][b[i+1]];
        mi[1].ind=par1[in][b[i+1]];
        mi[2].st=ot1+used2[in][b[i+1]];
        mi[2].ind=par2[in][b[i+1]];
        in=ind[b[i]][p2];
        if(!p2)in=ind[n+1][0];
        mi[3].st=ot2+used1[in][b[i+1]];
        mi[3].ind=par1[in][b[i+1]];
        mi[4].st=ot2+used2[in][b[i+1]];
        mi[4].ind=par2[in][b[i+1]];
        if(mi[1].st==ot1)mi[1].st=inf;
        if(mi[2].st==ot1)mi[2].st=inf;
        if(mi[3].st==ot2||!ot2)mi[3].st=inf;
        if(mi[4].st==ot2||!ot2)mi[4].st=inf;
        sort(mi+1,mi+5,cmp);
        ot1=mi[1].st;
        p1=mi[1].ind;
        if(mi[2].st!=inf&&mi[2].ind!=p1)
        {
            ot2=mi[2].st;
            p2=mi[2].ind;
        }
        else if(mi[3].st!=inf)
        {
            ot2=mi[3].st;
            p2=mi[3].ind;
        }
        else
        {
            ot2=0;
            p2=0;
        }
        //cout<<ot1<<" "<<ot2<<" "<<p1<<" "<<p2<<endl;
    }
    cout<<ot1<<endl;
}
void read()
{
    cin>>n>>m>>t>>k;
    for(long long int i=1;i<=m;i++)
    {
        cin>>a[i].from>>a[i].to>>a[i].st;
        v[a[i].from].push_back(a[i]);
        swap(a[i].from,a[i].to);
        v[a[i].from].push_back(a[i]);
    }
    prec();
    for(long long int i=1;i<=k;i++)
    {
        cin>>b[i];
    }
    for(long long int i=1;i<=t;i++)
    {
        cin>>c[i].ind>>c[i].st;
        b[c[i].ind]=c[i].st;
        resh();
    }
}
int main()
{
    speed();
    read();
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 0 / 38