Submission #867956

#	Time	Username	Problem	Language	Result	Execution time	Memory
867956		HuyQuang_re_Zero	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	509 ms	116816 KiB

crocodile

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define mxn 1000005
#include "crocodile.h"
using namespace std;
struct International_Olympiad_in_Informatics
{
    ll n,m,i,u,v,mn1[mxn],mn2[mxn],f[mxn];
    vector <II> a[mxn];
    const ll oo=1e18;
    int Work(int _n,int _m,int r[][2],int l[],int k,int p[])
    {

        n=_n; m=_m;
        for(i=1;i<=m;i++)
        {
            a[r[i][0]].push_back({ r[i][1],l[i] });
            a[r[i][1]].push_back({ r[i][0],l[i] });
        }

        for(u=1;u<=n;u++) f[u]=mn1[u]=mn2[u]=oo;
        set <II> s;
        for(i=1;i<=k;i++)
        {
            u=p[i];
            f[u]=mn1[u]=mn2[u]=0,s.insert({ f[u],u });
        }
        while(s.size()>0)
        {
            int u=s.begin()->snd; s.erase(s.begin());
            for(II adj:a[u])
            {
                int v=adj.fst,k=adj.snd;
                mn1[v]=min(mn1[v],f[u]+k);
                if(mn1[v]<mn2[v]) swap(mn1[v],mn2[v]);
                if(f[v]>mn1[v])
                {
                    s.erase({ f[v],v });
                    f[v]=mn1[v];
                    s.insert({ f[v],v });
                }
            }
        }
        return f[1];
    }
} IOI;

int travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
    for(int i=m;i>=1;i--)
    {
        r[i][0]=r[i-1][0]; r[i][1]=r[i-1][1];
        r[i][0]++; r[i][1]++;
        l[i]=l[i-1];
    }
    for(int i=k;i>=1;i--) p[i]=p[i-1],p[i]++;
    return IOI.Work(n,m,r,l,k,p);
}
/*
Write a procedure travel_plan(N,M,R,L,K,P) that takes the following parameters:
• N – the number of chambers. The chambers are numbered 0 through N-1.
• M – the number of corridors. The corridors are numbered 0 through M-1.
• R – a two-dimensional array of integers representing the corridors. For 0 ≤ i < M, corridor i connects two distinct chambers R[i][0] and R[i][1]. No two corridors join the same
pair of chambers.
• L – a one-dimensional array of integers containing the times needed to traverse the corridors. For 0 ≤ i < M, the value 1 ≤ L[i] ≤ 1 000 000 000 is the time Benjamas needs to runthrough the i
th corridor.
• K – the number of exit chambers. You may assume that 1 ≤ K < N.
• P – a one-dimensional array of integers with K distinct entries describing the exit chambers. For 0 ≤ i < K, the value P[i] is the number of the i
th exit chamber. Chamber 0 will
never be one of the exit chambers
*/
/*
int n,m,k,i,r[mxn][2],p[mxn],l[mxn];
int main()
{
    freopen("crocodile.inp","r",stdin);
    freopen("crocodile.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    for(i=0;i<m;i++) cin>>r[i][0]>>r[i][1]>>l[i];
    for(i=0;i<k;i++) cin>>p[i];
    cout<<travel_plan(n,m,r,l,k,p);
}
*/

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11