oj.uz

답안 #244049

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244049 2020-07-02T13:57:51 Z michao 꿈 (IOI13_dreaming) C++14
18 / 100
 65 ms 14840 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);
	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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 14840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 14840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 14840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 6528 KB Output is correct
2 Correct 29 ms 6528 KB Output is correct
3 Correct 29 ms 6528 KB Output is correct
4 Correct 32 ms 6528 KB Output is correct
5 Correct 28 ms 6400 KB Output is correct
6 Correct 37 ms 6912 KB Output is correct
7 Correct 30 ms 6656 KB Output is correct
8 Correct 34 ms 6400 KB Output is correct
9 Correct 31 ms 6400 KB Output is correct
10 Correct 37 ms 6520 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 10 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 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 2816 KB Output is correct
23 Correct 9 ms 4220 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 14840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 14840 KB Output isn't correct
2 Halted 0 ms 0 KB -