oj.uz

Submission #867956

# Submission time Handle Problem Language Result Execution time Memory
867956 2023-10-30T01:51:20 Z HuyQuang_re_Zero Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 509 ms 116816 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 6 ms 31220 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31068 KB Output is correct
7 Correct 6 ms 31164 KB Output is correct
8 Correct 6 ms 31324 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 6 ms 31220 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31068 KB Output is correct
7 Correct 6 ms 31164 KB Output is correct
8 Correct 6 ms 31324 KB Output is correct
9 Correct 7 ms 31580 KB Output is correct
10 Correct 6 ms 31224 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 9 ms 33636 KB Output is correct
13 Correct 10 ms 33884 KB Output is correct
14 Correct 7 ms 31068 KB Output is correct
15 Correct 7 ms 31228 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 6 ms 31220 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31068 KB Output is correct
7 Correct 6 ms 31164 KB Output is correct
8 Correct 6 ms 31324 KB Output is correct
9 Correct 7 ms 31580 KB Output is correct
10 Correct 6 ms 31224 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 9 ms 33636 KB Output is correct
13 Correct 10 ms 33884 KB Output is correct
14 Correct 7 ms 31068 KB Output is correct
15 Correct 7 ms 31228 KB Output is correct
16 Correct 393 ms 111308 KB Output is correct
17 Correct 64 ms 50516 KB Output is correct
18 Correct 108 ms 52816 KB Output is correct
19 Correct 509 ms 116816 KB Output is correct
20 Correct 236 ms 97104 KB Output is correct
21 Correct 37 ms 43096 KB Output is correct
22 Correct 260 ms 96100 KB Output is correct