oj.uz

Submission #244037

# Submission time Handle Problem Language Result Execution time Memory
244037 2020-07-02T13:49:06 Z michao Dreaming (IOI13_dreaming) C++14
18 / 100
 64 ms 14712 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
using namespace std;
const int MAX=1e5+5;
vector<pii>P[MAX];
int dist[MAX];
int ojciec[MAX];
vi mids;
bool O[MAX];

pii get_far(int u,int fa)
{
	pii akt=mp(dist[u],u);
	ojciec[u]=fa;
	O[u]=true;
  for (auto it:P[u])
  	if (it.st!=fa)
  	{
  		dist[it.st]=dist[fa]+it.nd;
  		pii wez=get_far(it.st,u);
  		if (wez.st>akt.st)akt=wez;
  	}
  return akt;
}

int get_mid(int from,int ile)
{
	int maxi=0;
	while (from!=-1)
	{
		maxi=max(maxi,max(dist[from],ile-dist[from]));
		from=ojciec[from];
	}
	return maxi;
}

void func(int u)
{
	dist[u]=0;
	pii v=get_far(u,-1);
	int root=v.nd;
	pii znajdz=get_far(root,-1);
	int dist=znajdz.st;
	int wskaz=znajdz.nd;
  int ile=get_mid(wskaz,dist);
	mids.pb(ile);
}

int travelTime(int n,int m,int l,int a[],int b[],int t[])
{
	int ans=0;
	for (int i=0;i<m;i++)
	{
		int x=a[i];
		int y=b[i];
		int c=t[i];
		x++,y++;
		P[x].pb(mp(y,c));
		P[y].pb(mp(x,c));
	}
	
	for (int i=1;i<=n;i++)
	   if (!O[i])func(i);
	sort(mids.begin(),mids.end(),greater<int>());
	assert(sz(mids)!=0);
	if (sz(mids)>=1)ans=max(ans,mids[0]);
	if (sz(mids)>=2)ans=max(ans,mids[0]+mids[1]+l);
	if (sz(mids)>=3)ans=max(ans,mids[1]+mids[2]+l*2);
	return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 14712 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 33 ms 6400 KB Output is correct
2 Correct 30 ms 6520 KB Output is correct
3 Correct 32 ms 6528 KB Output is correct
4 Correct 30 ms 6528 KB Output is correct
5 Correct 28 ms 6400 KB Output is correct
6 Correct 30 ms 6912 KB Output is correct
7 Correct 31 ms 6656 KB Output is correct
8 Correct 33 ms 6400 KB Output is correct
9 Correct 28 ms 6392 KB Output is correct
10 Correct 30 ms 6656 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 9 ms 4220 KB Output is correct
13 Correct 14 ms 4220 KB Output is correct
14 Correct 10 ms 4220 KB Output is correct
15 Correct 10 ms 4220 KB Output is correct
16 Correct 10 ms 4220 KB Output is correct
17 Correct 10 ms 4092 KB Output is correct
18 Correct 10 ms 4220 KB Output is correct
19 Correct 10 ms 4220 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 4220 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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