oj.uz

Submission #897393

# Submission time Handle Problem Language Result Execution time Memory
897393 2024-01-03T03:27:00 Z Faisal_Saqib Dreaming (IOI13_dreaming) C++17
10 / 100
 34 ms 13144 KB 
#include "dreaming.h"
#include <iostream>
#include <vector>
using namespace std; 
const int N=1e5+200;
vector<pair<int,int>> ma[N];
bool vis[N];
int dp_down[N][2];
int dp_up[N];
int mxx[N];
int n,m,l;
void dfs_down(int x,int p=-1)
{
	vis[x]=1;
	dp_down[x][0]=dp_down[x][1]=0;
	for(auto [w,y]:ma[x])
	{
		if(y!=p)
		{
			dfs_down(y,x);
			int cur=dp_down[y][0]+w;
			if(dp_down[x][0]<cur)
			{
				dp_down[x][1]=dp_down[x][0];
				dp_down[x][0]=cur;
			}
			else if(dp_down[x][1]<cur)
			{
				dp_down[x][1]=cur;
			}
		}
	}
}
int vertex=-1;
int dist=2e9;
int cp=-1;
void dfs_up(int x,int p=-1)
{
	mxx[x]=max(dp_up[x],dp_down[x][0]);
	cp=max(cp,mxx[x]);
	if(mxx[x]<dist)
	{
		dist=mxx[x];
		vertex=x;
	}
	for(auto [w,y]:ma[x])
	{
		if(y!=p)
		{
			dp_up[y]=max(dp_up[y],dp_up[x]+w);
			if(dp_down[x][0]==(dp_down[y][0]+w))
				dp_up[y]=max(dp_up[y],dp_down[x][1]+w);
			else
				dp_up[y]=max(dp_up[y],dp_down[x][0]+w);
			dfs_up(y,x);
		}
	}
}
int travelTime(int N, int M, int L, int a[], int b[], int t[])
{
	n=N;
	m=M;
	l=L;
	for(int i=0;i<m;i++)
	{
		ma[a[i]].push_back({t[i],b[i]});
		ma[b[i]].push_back({t[i],a[i]});
	}
	for(int i=0;i<n;i++)
	{
		if(!vis[i]){
			int bv=vertex;
			int bd=dist;
			vertex=-1;
			dist=2e9;
			dfs_down(i);
			dfs_up(i);
			if(bv!=-1)
			{
				ma[bv].push_back({l,vertex});
				ma[vertex].push_back({l,bv});
				if(dist<=bd)
				{
					vertex=bv;
					dist=bd;
				}
			}
		}
	}
	cp=-1;
	dfs_down(0);
	dfs_up(0);
	return cp;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12632 KB Output is correct
2 Correct 34 ms 13144 KB Output is correct
3 Correct 23 ms 12368 KB Output is correct
4 Correct 6 ms 6492 KB Output is correct
5 Incorrect 7 ms 5976 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 1 ms 5208 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 2 ms 5456 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 1 ms 5212 KB Output is correct
15 Correct 1 ms 5212 KB Output is correct
16 Correct 1 ms 5212 KB Output is correct
17 Correct 1 ms 5468 KB Output is correct
18 Correct 1 ms 5212 KB Output is correct
19 Correct 1 ms 5212 KB Output is correct
20 Correct 1 ms 5212 KB Output is correct
21 Correct 1 ms 5212 KB Output is correct
22 Correct 1 ms 5212 KB Output is correct
23 Correct 1 ms 5464 KB Output is correct
24 Correct 1 ms 5212 KB Output is correct
25 Correct 1 ms 5468 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12632 KB Output is correct
2 Correct 34 ms 13144 KB Output is correct
3 Correct 23 ms 12368 KB Output is correct
4 Correct 6 ms 6492 KB Output is correct
5 Incorrect 7 ms 5976 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8916 KB Output is correct
2 Incorrect 17 ms 9432 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 1 ms 5208 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 1 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5212 KB Output is correct
11 Correct 1 ms 5212 KB Output is correct
12 Correct 2 ms 5456 KB Output is correct
13 Correct 2 ms 5212 KB Output is correct
14 Correct 1 ms 5212 KB Output is correct
15 Correct 1 ms 5212 KB Output is correct
16 Correct 1 ms 5212 KB Output is correct
17 Correct 1 ms 5468 KB Output is correct
18 Correct 1 ms 5212 KB Output is correct
19 Correct 1 ms 5212 KB Output is correct
20 Correct 1 ms 5212 KB Output is correct
21 Correct 1 ms 5212 KB Output is correct
22 Correct 1 ms 5212 KB Output is correct
23 Correct 1 ms 5464 KB Output is correct
24 Correct 1 ms 5212 KB Output is correct
25 Correct 1 ms 5468 KB Output is correct
26 Correct 2 ms 5464 KB Output is correct
27 Correct 2 ms 5468 KB Output is correct
28 Correct 2 ms 5484 KB Output is correct
29 Correct 2 ms 5464 KB Output is correct
30 Correct 2 ms 5468 KB Output is correct
31 Correct 2 ms 5464 KB Output is correct
32 Correct 1 ms 5468 KB Output is correct
33 Incorrect 2 ms 5468 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12632 KB Output is correct
2 Correct 34 ms 13144 KB Output is correct
3 Correct 23 ms 12368 KB Output is correct
4 Correct 6 ms 6492 KB Output is correct
5 Incorrect 7 ms 5976 KB Output isn't correct
6 Halted 0 ms 0 KB -