Submission #228159

#	Time	Username	Problem	Language	Result	Execution time	Memory
228159		bharat2002	Dreaming (IOI13_dreaming)	C++14	18 / 100	65 ms	13304 KiB

dreaming

/*input
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
const int inf=2e9;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
vector< pii > adjlist[N];int dp[N][2], ext[N];vector<int> vals;
queue<int> nodes;
void dfs1(int i, int p)
{
	dp[i][0]=0;ext[i]=0;
	for(auto j:adjlist[i])
	{
		if(j.f==p) continue;
		dfs1(j.f, i);
		ext[i]=max(ext[i], min(dp[i][0], dp[j.f][0] + j.s));
		dp[i][0]=max(dp[i][0], dp[j.f][0]+ j.s);
	}
}
void dfs2(int i, int pv)
{
	nodes.push(i);
	dp[i][1]=max(dp[i][0], pv);
	for(auto j:adjlist[i])
	{
		if(dp[j.f][1]!=-1) continue;
		if(pv==0)
		{
			if(dp[i][0]==dp[j.f][0]+ j.s) dfs2(j.f, ext[i]+j.s);
			else dfs2(j.f, dp[i][0]+j.s);
		}
		else dfs2(j.f, pv + j.s);
	}
}
int travelTime(int n, int m, int l, int a[], int b[], int c[])
{
	for(int i=0;i<m;i++)
	{
		adjlist[a[i]+1].push_back(mp(b[i]+1, c[i]));adjlist[b[i]+1].push_back(mp(a[i]+1, c[i]));
	}
	dp[0][0]=dp[0][1]=inf;
	for(int i=1;i<=n;i++) dp[i][0]=dp[i][1]=-1;
	for(int i=1;i<=n;i++)
	{
		if(dp[i][0]!=-1) continue;
		dfs1(i, 0);dfs2(i, 0);int cn=0;
		while(!nodes.empty())
		{
			int cur=nodes.front();nodes.pop();
			if(dp[cur][1]<dp[cn][1])
			{
				cn=cur;
			}
		}
		//cout<<cn-1<<":"<<dp[cn][1]<<"\n";
		vals.push_back(dp[cn][1]);
	}
	//cout<<endl;
	//cout<<1<<":"<<dp[2][0]<<" "<<ext[2]<<endl;
	sort(vals.begin(), vals.end());reverse(vals.begin(), vals.end());
	if(vals.size()==1) return vals[0];
	int ret=vals[0]+vals[1]+l;
	if(vals.size()==2) return ret;
	ret=max(ret, vals[1] + vals[2] + 2*l);return ret;
}
/*signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, m, l, a[N], b[N], c[N];
	cin>>n>>m>>l;
	for(int i=0;i<m;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
	}
	cout<<travelTime(n, m, l, a, b, c);
}*/

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