oj.uz

Submission #244067

# Submission time Handle Problem Language Result Execution time Memory
244067 2020-07-02T14:15:24 Z michao Dreaming (IOI13_dreaming) C++14
18 / 100
 63 ms 14584 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;
const int inf=INT_MAX;
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[u]+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=inf;
	while (from!=-1)
	{
		maxi=min(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;
	dist[root]=0;
	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 63 ms 14584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 14584 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 6272 KB Output is correct
2 Correct 29 ms 6400 KB Output is correct
3 Correct 29 ms 6144 KB Output is correct
4 Correct 29 ms 6272 KB Output is correct
5 Correct 28 ms 6272 KB Output is correct
6 Correct 30 ms 6656 KB Output is correct
7 Correct 31 ms 6400 KB Output is correct
8 Correct 27 ms 6144 KB Output is correct
9 Correct 28 ms 6144 KB Output is correct
10 Correct 29 ms 6400 KB Output is correct
11 Correct 6 ms 2816 KB Output is correct
12 Correct 11 ms 4220 KB Output is correct
13 Correct 10 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 63 ms 14584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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