Submission #987313

#	Time	Username	Problem	Language	Result	Execution time	Memory
987313		aaaaaarroz	Dreaming (IOI13_dreaming)	C++17	100 / 100	90 ms	24748 KiB

dreaming

    #include "dreaming.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define mp make_pair
    #define fr first
    #define sc second
     
    long long nn=0,mx,vtd[100069],bg[3],inf=1e18;
    vector<pair<long long,long long>> al[100069];
    pair<long long,long long> dp[100069];
     
    void dfs(long long ky,long long x)
    {
    	long long i,sz=al[x].size(),l,w;
    	
    	vtd[x]=ky;
    	dp[x]={0,x};
    	for(i=0;i<sz;i++)
    	{
    		l=al[x][i].fr;
    		w=al[x][i].sc;
    		if(vtd[l]!=ky)
    		{
    			dfs(ky,l);
    			dp[x]=max(dp[x],{dp[l].fr+w,l});
    		}
    	}
    }
     
    int travelTime(int n,int m,int d,int ka[],int la[],int wg[])
    {
    	long long i,j,r,k,l,w,p,mn;
    	
    	for(i=0;i<m;i++)
    	{
    		k=ka[i];
    		l=la[i];
    		w=wg[i];
    		al[k].push_back({l,w});
    		al[l].push_back({k,w});
    	}
    	mx=-inf;
    	for(i=0;i<3;i++)
    	{
    		bg[i]=-inf;
    	}
    	for(i=0;i<n;i++)
    	{
    		if(!vtd[i])
    		{
    			dfs(1,i);
    			for(p=i;dp[p].sc!=p;p=dp[p].sc);
    			dfs(2,p);
    			w=dp[p].fr;
    			mx=max(mx,w);
    			mn=inf;
    			for(;1;p=dp[p].sc)
    			{
    				mn=min(mn,max(dp[p].fr,w-dp[p].fr));
    				if(dp[p].sc==p)
    				{
    					break;
    				}
    			}
    			for(j=0;j<3;j++)
    			{
    				if(mn>bg[j])
    				{
    					for(r=2;r>j;r--)
    					{
    						bg[r]=bg[r-1];
    					}
    					bg[j]=mn;
    					break;
    				}
    			}
    		}
    	}
    	return max(mx,max(bg[0],bg[2]+d)+bg[1]+d);
    }

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23