oj.uz

Submission #244061

# Submission time Handle Problem Language Result Execution time Memory
244061 2020-07-02T14:07:06 Z michao Dreaming (IOI13_dreaming) C++14
0 / 100
 63 ms 15736 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[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=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;
	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);
	assert(mids[0]!=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 15736 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 15736 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 15736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6648 KB Output is correct
2 Correct 38 ms 6648 KB Output is correct
3 Correct 29 ms 6656 KB Output is correct
4 Correct 31 ms 6656 KB Output is correct
5 Correct 29 ms 6648 KB Output is correct
6 Correct 31 ms 7168 KB Output is correct
7 Correct 31 ms 6784 KB Output is correct
8 Correct 29 ms 6520 KB Output is correct
9 Correct 28 ms 6528 KB Output is correct
10 Correct 30 ms 6784 KB Output is correct
11 Correct 7 ms 2688 KB Output is correct
12 Correct 9 ms 4220 KB Output is correct
13 Correct 10 ms 4220 KB Output is correct
14 Correct 9 ms 4220 KB Output is correct
15 Correct 9 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 11 ms 4348 KB Output is correct
19 Correct 10 ms 4220 KB Output is correct
20 Runtime error 9 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 15736 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 15736 KB Output isn't correct
2 Halted 0 ms 0 KB -