oj.uz

Submission #133536

# Submission time Handle Problem Language Result Execution time Memory
133536 2019-07-21T04:02:40 Z tinjyu Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 6 ms 1016 KB 
#include "crocodile.h"
#include <iostream>
using namespace std;
long long int headnow[1000005],e=0,tag[1000005],head[1000005],ans[1000005][2],n,m,map[2000005][3],road[1000005];
int travel_plan(int N, int M, int r[][2], int l[], int k, int p[])
{
    n=N;
    m=M;
    for(int i=0;i<n;i++)road[i]=-1;
    for(int i=0;i<m;i++)
    {
        int x=r[i][0],y=r[i][1];
        map[i*2][0]=y;
        map[i*2][1]=road[x];
        map[i*2][2]=l[i];
        road[x]=i*2;
        map[i*2+1][0]=x;
        map[i*2+1][1]=road[y];
        map[i*2+1][2]=l[i];
        road[y]=i*2+1;
    }
    for(int i=0;i<n;i++)
    {
        ans[i][0]=999999999999999;
        ans[i][1]=999999999999999;
    }
    e=k;
    for(int i=0;i<k;i++)
    {
        ans[p[i]][0]=0;
        ans[p[i]][1]=0;
        tag[p[i]]=1;
        head[i+1]=p[i];
        headnow[p[i]]=i;
    }
    while(e>0)
    {
        int x=head[1];
		swap(head[1],head[e]);
        e--;
        headnow[head[e]]=1;
        int pe=1;
        while(pe*2<=e)
        {
            if(ans[head[pe]][1]>ans[head[pe*2]][1] || ans[head[pe]][1]>ans[head[pe*2+1]][1])
            {
                if(ans[head[pe*2+1]][1]<ans[head[pe*2]][1] && pe*2+1<=e)
                {
                	headnow[head[pe]]=pe*2+1;
                	headnow[head[pe*2+1]]=pe;
                    swap(head[pe],head[pe*2+1]);
                    pe=pe*2+1;
                }
                else
                {
                	headnow[head[pe]]=pe*2;
                	headnow[head[pe*2]]=pe;
                    swap(head[pe],head[pe*2]);
                    pe=pe*2;
                }
            }
            else break;
        }
        int g=road[x];
 
        while(g!=-1)
        {
            	int now=map[g][0];
                long long int tmp=ans[x][1]+map[g][2];
                long long int t=ans[now][1];
                if(tmp<ans[now][0])
                {
                    ans[now][1]=ans[now][0];
                    ans[now][0]=tmp;
                }
                else if(tmp<ans[now][1])
                {
                    ans[now][1]=tmp;
                }
                if(ans[now][1]!=999999999999999 && tag[now]==0)
                {
                    tag[now]=1;
                    e++;
                    head[e]=now;
                    int pe=e;
                    while(pe>1)
                    {
                        if(ans[head[pe]][1]<ans[head[pe/2]][1])
                        {
                        	headnow[head[pe]]=pe/2;
                        	headnow[head[pe/2]]=pe;
                            swap(head[pe],head[pe/2]);
                            pe/=2;
                        }
                        else break;
                    }
                }
                else if(ans[now][1]<t)
                {
                	int pe=headnow[now];
                    while(pe>1)
                    {
                        if(ans[head[pe]][1]<ans[head[pe/2]][1])
                        {
                        	headnow[head[pe]]=pe/2;
                        	headnow[head[pe/2]]=pe;
                            swap(head[pe],head[pe/2]);
                            pe/=2;
                        }
                        else break;
                    }
				}
            g=map[g][1];
        }
    }
    return ans[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 2 ms 504 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Incorrect 6 ms 1016 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 424 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Incorrect 6 ms 1016 KB Output isn't correct
13 Halted 0 ms 0 KB -