oj.uz

Submission #228159

# Submission time Handle Problem Language Result Execution time Memory
228159 2020-04-30T05:37:31 Z bharat2002 Dreaming (IOI13_dreaming) C++14
18 / 100
 65 ms 13304 KB 
/*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.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6904 KB Output is correct
2 Correct 29 ms 6904 KB Output is correct
3 Correct 31 ms 6912 KB Output is correct
4 Correct 30 ms 6912 KB Output is correct
5 Correct 31 ms 7040 KB Output is correct
6 Correct 30 ms 7416 KB Output is correct
7 Correct 28 ms 7040 KB Output is correct
8 Correct 28 ms 6912 KB Output is correct
9 Correct 27 ms 6784 KB Output is correct
10 Correct 31 ms 7040 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 9 ms 4476 KB Output is correct
13 Correct 10 ms 4604 KB Output is correct
14 Correct 9 ms 4472 KB Output is correct
15 Correct 9 ms 4472 KB Output is correct
16 Correct 10 ms 4472 KB Output is correct
17 Correct 10 ms 4476 KB Output is correct
18 Correct 9 ms 4600 KB Output is correct
19 Correct 9 ms 4476 KB Output is correct
20 Correct 6 ms 2688 KB Output is correct
21 Correct 6 ms 2688 KB Output is correct
22 Correct 6 ms 2816 KB Output is correct
23 Correct 9 ms 4604 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -