답안 #228170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228170	2020-04-30T05:50:48 Z	bharat2002	꿈 (IOI13_dreaming)	C++14	32 / 100	68 ms	13176 KB

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;int ret;
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);
	}
	ret=max(ret, dp[i][0] + ext[i]);
}
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;
	ret=0;
	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 ret;
	ret=max(vals[0]+vals[1]+l, ret);
	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
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	13176 KB	Output is correct
2	Correct	68 ms	12920 KB	Output is correct
3	Correct	43 ms	11132 KB	Output is correct
4	Correct	13 ms	4224 KB	Output is correct
5	Correct	11 ms	3584 KB	Output is correct
6	Correct	19 ms	4992 KB	Output is correct
7	Correct	6 ms	2688 KB	Output is correct
8	Correct	35 ms	7160 KB	Output is correct
9	Correct	39 ms	9336 KB	Output is correct
10	Correct	6 ms	2816 KB	Output is correct
11	Correct	66 ms	10488 KB	Output is correct
12	Correct	68 ms	11768 KB	Output is correct
13	Correct	6 ms	2816 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	13176 KB	Output is correct
2	Correct	68 ms	12920 KB	Output is correct
3	Correct	43 ms	11132 KB	Output is correct
4	Correct	13 ms	4224 KB	Output is correct
5	Correct	11 ms	3584 KB	Output is correct
6	Correct	19 ms	4992 KB	Output is correct
7	Correct	6 ms	2688 KB	Output is correct
8	Correct	35 ms	7160 KB	Output is correct
9	Correct	39 ms	9336 KB	Output is correct
10	Correct	6 ms	2816 KB	Output is correct
11	Correct	66 ms	10488 KB	Output is correct
12	Correct	68 ms	11768 KB	Output is correct
13	Correct	6 ms	2816 KB	Output is correct
14	Correct	6 ms	2688 KB	Output is correct
15	Correct	6 ms	2688 KB	Output is correct
16	Incorrect	6 ms	2688 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	13176 KB	Output is correct
2	Correct	68 ms	12920 KB	Output is correct
3	Correct	43 ms	11132 KB	Output is correct
4	Correct	13 ms	4224 KB	Output is correct
5	Correct	11 ms	3584 KB	Output is correct
6	Correct	19 ms	4992 KB	Output is correct
7	Correct	6 ms	2688 KB	Output is correct
8	Correct	35 ms	7160 KB	Output is correct
9	Correct	39 ms	9336 KB	Output is correct
10	Correct	6 ms	2816 KB	Output is correct
11	Correct	66 ms	10488 KB	Output is correct
12	Correct	68 ms	11768 KB	Output is correct
13	Correct	6 ms	2816 KB	Output is correct
14	Correct	6 ms	2688 KB	Output is correct
15	Correct	6 ms	2688 KB	Output is correct
16	Incorrect	6 ms	2688 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	29 ms	6912 KB	Output is correct
2	Correct	29 ms	6904 KB	Output is correct
3	Correct	28 ms	6912 KB	Output is correct
4	Correct	29 ms	6912 KB	Output is correct
5	Correct	29 ms	6912 KB	Output is correct
6	Correct	34 ms	7424 KB	Output is correct
7	Correct	30 ms	7168 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	7092 KB	Output is correct
11	Correct	6 ms	2688 KB	Output is correct
12	Correct	10 ms	4604 KB	Output is correct
13	Correct	10 ms	4604 KB	Output is correct
14	Correct	9 ms	4472 KB	Output is correct
15	Correct	10 ms	4472 KB	Output is correct
16	Correct	10 ms	4472 KB	Output is correct
17	Correct	9 ms	4476 KB	Output is correct
18	Correct	10 ms	4600 KB	Output is correct
19	Correct	10 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	2688 KB	Output is correct
23	Correct	10 ms	4604 KB	Output is correct

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	13176 KB	Output is correct
2	Correct	68 ms	12920 KB	Output is correct
3	Correct	43 ms	11132 KB	Output is correct
4	Correct	13 ms	4224 KB	Output is correct
5	Correct	11 ms	3584 KB	Output is correct
6	Correct	19 ms	4992 KB	Output is correct
7	Correct	6 ms	2688 KB	Output is correct
8	Correct	35 ms	7160 KB	Output is correct
9	Correct	39 ms	9336 KB	Output is correct
10	Correct	6 ms	2816 KB	Output is correct
11	Correct	66 ms	10488 KB	Output is correct
12	Correct	68 ms	11768 KB	Output is correct
13	Correct	6 ms	2816 KB	Output is correct
14	Correct	6 ms	2688 KB	Output is correct
15	Correct	7 ms	2816 KB	Output is correct
16	Correct	7 ms	2944 KB	Output is correct
17	Correct	6 ms	2688 KB	Output is correct
18	Correct	6 ms	2816 KB	Output is correct
19	Correct	7 ms	2944 KB	Output is correct
20	Correct	6 ms	2816 KB	Output is correct
21	Correct	9 ms	2816 KB	Output is correct
22	Correct	7 ms	2944 KB	Output is correct
23	Correct	6 ms	2688 KB	Output is correct
24	Correct	6 ms	2688 KB	Output is correct
25	Correct	6 ms	2688 KB	Output is correct
26	Incorrect	6 ms	2688 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	13176 KB	Output is correct
2	Correct	68 ms	12920 KB	Output is correct
3	Correct	43 ms	11132 KB	Output is correct
4	Correct	13 ms	4224 KB	Output is correct
5	Correct	11 ms	3584 KB	Output is correct
6	Correct	19 ms	4992 KB	Output is correct
7	Correct	6 ms	2688 KB	Output is correct
8	Correct	35 ms	7160 KB	Output is correct
9	Correct	39 ms	9336 KB	Output is correct
10	Correct	6 ms	2816 KB	Output is correct
11	Correct	66 ms	10488 KB	Output is correct
12	Correct	68 ms	11768 KB	Output is correct
13	Correct	6 ms	2816 KB	Output is correct
14	Correct	6 ms	2688 KB	Output is correct
15	Correct	6 ms	2688 KB	Output is correct
16	Incorrect	6 ms	2688 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

답안 #228170

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 0 / 10.0

Subtask #3 0 / 23.0

Subtask #4 18.0 / 18.0

Subtask #5 0 / 12.0

Subtask #6 0 / 23.0

Subtask #1
14.0 / 14.0

Subtask #2
0 / 10.0

Subtask #3
0 / 23.0

Subtask #4
18.0 / 18.0

Subtask #5
0 / 12.0

Subtask #6
0 / 23.0