oj.uz

Submission #271232

# Submission time Handle Problem Language Result Execution time Memory
271232 2020-08-18T05:17:12 Z anubhavdhar Dreaming (IOI13_dreaming) C++11
18 / 100
 62 ms 15096 KB 
#include<bits/stdc++.h>

#include "dreaming.h"

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;
/*
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;*/

#define INF 1000000000000000006
#define MAXN 100005

ll N, M, cen, mxdep, par[MAXN], ext1, ext2, depth[MAXN], K;
vll g[MAXN];
bool vis[MAXN];

void dfs1(int a, int dep)
{
	if(mxdep < dep)
		mxdep = dep, ext1 = a;
	for(pll bb : g[a])
		if(!vis[bb.ff])
			vis[bb.ff] = true, dfs1(bb.ff, dep + bb.ss);
}

void dfs2(int a, int p, int dep)
{
	// cerr<<a<<' ';
	if(mxdep < dep)
		mxdep = dep, ext2 = a;
	par[a] = p;
	depth[a] = dep;
	for(pll bb : g[a])
		if(bb.ff != p)
			dfs2(bb.ff, a, bb.ss + dep);
}

void dfs3(int a)
{
	if(a == -1)
		return;
	if(mxdep > max(depth[a], depth[ext2] - depth[a]))
		mxdep = max(depth[a], depth[ext2] - depth[a]), cen = a;
	dfs3(par[a]);
}

vi Lenghts;

int solve()
{
	F0R(i, N)
		vis[i] = false;

	F0R(i, N)
	{
		if(!vis[i])
		{
			// cerr<<"not cisited["<<i<<"]\n";
			vis[i] = true;
			mxdep = -1;
			dfs1(i, 0);
			mxdep = -1;
			dfs2(ext1, -1, 0);
			mxdep = INF;
			dfs3(ext2);
			Lenghts.pb(mxdep);
			// cerr<<"\nmxdep = "<<mxdep<<", ext1 = "<<ext1<<", ext2 = "<<ext2<<'\n';
		}
	}

	sort(all(Lenghts), greater<ll>());
	ll ans;
	if((int)Lenghts.size() == 1)
		ans = Lenghts[0];
	else if ((int)Lenghts.size() == 2)
		ans = Lenghts[1] + Lenghts[0] + K;
	else
		ans = max(Lenghts[1] + K + Lenghts[0], Lenghts[1] + 2*K + Lenghts[2]);
	return ans;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
	N = n;
	M = m;
	K = L;
	F0R(i, M)
		g[A[i]].pb(mp(B[i], T[i])), g[B[i]].pb(mp(A[i], T[i]));
	return solve();
}

/*signed main()
{

	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	int n, m, L;
	cin>>n>>m>>L;
	int A[m], B[m], T[m];

	F0R(i, m)
		cin>>A[i]>>B[i]>>T[i];

	cout<<travelTime(n, m, L, A, B, T)<<'\n';

	return 0;
}*/

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 15096 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 7424 KB Output is correct
2 Correct 38 ms 7424 KB Output is correct
3 Correct 29 ms 7420 KB Output is correct
4 Correct 34 ms 7368 KB Output is correct
5 Correct 28 ms 7424 KB Output is correct
6 Correct 37 ms 7928 KB Output is correct
7 Correct 31 ms 7544 KB Output is correct
8 Correct 30 ms 7296 KB Output is correct
9 Correct 30 ms 7288 KB Output is correct
10 Correct 33 ms 7544 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 8 ms 4988 KB Output is correct
13 Correct 7 ms 4988 KB Output is correct
14 Correct 7 ms 4860 KB Output is correct
15 Correct 8 ms 4860 KB Output is correct
16 Correct 7 ms 4860 KB Output is correct
17 Correct 8 ms 4856 KB Output is correct
18 Correct 7 ms 4988 KB Output is correct
19 Correct 6 ms 4860 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Correct 2 ms 2816 KB Output is correct
23 Correct 7 ms 4860 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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