oj.uz

답안 #244071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244071 2020-07-02T14:21:52 Z michao 꿈 (IOI13_dreaming) C++14
0 / 100
 62 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;
	assert(from!=-1);
	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));
	}
	int ile=0;
	for (int i=1;i<=n;i++)
	   if (!O[i])func(i),ile++;
	assert(ile<n);
	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 62 ms 14584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 6272 KB Output is correct
2 Correct 29 ms 6264 KB Output is correct
3 Correct 28 ms 6272 KB Output is correct
4 Correct 31 ms 6264 KB Output is correct
5 Correct 27 ms 6272 KB Output is correct
6 Correct 32 ms 6656 KB Output is correct
7 Correct 34 ms 6400 KB Output is correct
8 Correct 30 ms 6144 KB Output is correct
9 Correct 27 ms 6144 KB Output is correct
10 Correct 32 ms 6520 KB Output is correct
11 Correct 6 ms 2688 KB Output is correct
12 Correct 10 ms 4220 KB Output is correct
13 Correct 10 ms 4220 KB Output is correct
14 Correct 11 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 9 ms 4092 KB Output is correct
18 Correct 13 ms 4348 KB Output is correct
19 Correct 9 ms 4220 KB Output is correct
20 Runtime error 9 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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