oj.uz

Submission #133537

# Submission time Handle Problem Language Result Execution time Memory
133537 2019-07-21T04:07:07 Z tinjyu Crocodile's Underground City (IOI11_crocodile) C++14
89 / 100
 706 ms 77272 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]<t)
                {
                	if(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
                	{
                		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];
        }
        tag[x]=0;
    }
    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 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct

Subtask #2
43.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 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 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 Correct 6 ms 1016 KB Output is correct
13 Correct 5 ms 1020 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct

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 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 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 Correct 6 ms 1016 KB Output is correct
13 Correct 5 ms 1020 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Incorrect 706 ms 77272 KB Output isn't correct
17 Halted 0 ms 0 KB -