oj.uz

Submission #336622

# Submission time Handle Problem Language Result Execution time Memory
336622 2020-12-16T03:29:26 Z arwaeystoamneg Dreaming (IOI13_dreaming) C++17
18 / 100
 97 ms 20460 KB 
#include "dreaming.h"
/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "My name's Ozymandias, king of kings: look on my works, ye mighty and despair!" <<endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }

int n, m, l, maxdia;
vector<vpi>adj;
vi depth, parents, type;
int cur;
void depth_(int i, int p)
{
	parents[i] = p;
	depth[i] = 0, type[i] = cur;
	trav(x, adj[i])
	{
		if (x.f != p)
		{
			depth_(x.f, i);
			depth[i] = max(depth[i], depth[x.f] + x.s);
		}
	}
}
vi up;
void up_(int i, int p)
{
	up[i] = max(0, up[i]);
	multiset<int, greater<int>>t = { up[i] };
	trav(x, adj[i])
	{
		if (x.f != p)
		{
			t.insert(x.s + depth[x.f]);
		}
	}
	trav(x, adj[i])
	{
		if (x.f != p)
		{
			t.erase(t.find(x.s + depth[x.f]));
			up[x.f] = x.s + *t.begin();
			t.insert(x.s + depth[x.f]);
		}
	}
	trav(x, adj[i])
	{
		if (x.f != p)
		{
			up_(x.f, i);
		}
	}
}
int travelTime(int a, int b, int c, int* d, int* e, int* f)
{
	n = a;
	m = b;
	l = c;
	adj.rsz(n);
	F0R(i, m)
	{
		adj[d[i]].pb({ e[i],f[i] });
		adj[e[i]].pb({ d[i],f[i] });
	}/*
	if (n == 1)
	{
		return 0;
	}
	if (n == 2)
	{
		return m == 1 ? adj[0][0].s : l;
	}*/
	depth.rsz(n, -1);
	parents.rsz(n);
	type.rsz(n);
	F0R(i, n)
	{
		if (depth[i] == -1)depth_(i, -1), cur++;
	}
	F0R(i, n)
	{
		int a = 0, b = 0;
		trav(x, adj[i])
		{
			if (x.f != parents[i])
			{
				if (a == 0)a = depth[x.f] + x.s;
				else if (b == 0)
				{
					if (a > depth[x.f] + x.s)
						b = depth[x.f] + x.s;
					else
					{
						b = a;
						a = depth[x.f];
					}
				}
				else
				{
					if (depth[x.f] + x.s >= a) { b = a; a = depth[x.f] + x.s; }
					else if (depth[x.f] + x.s >= b)b = depth[x.f] + x.s;
				}
			}
		}
		maxdia = max(maxdia, a + b);
	}
	up.rsz(n, -1);
	F0R(i, n)
	{
		if (up[i] == -1)up_(i, -1);
	}
	vi size(cur, inf);
	F0R(i, n)
	{		
		multiset<int>t;
		trav(x, adj[i])
		{
			if (x.f != parents[i])
			{
				t.insert(x.s + depth[x.f]);
			}
		}
		t.insert(up[i]);
		if (sz(t) == 1)continue;
		size[type[i]] = min(size[type[i]], *t.rbegin());
	}
	trav(x, size)if (x == inf)x = 0;
	sort(all(size), greater<int>());
	return max({ maxdia,sz(size) > 1 ? size[0] + size[1] + l : 0, sz(size) > 2 ? size[1] + size[2] + 2 * l : 0 });
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 20460 KB Output is correct
2 Incorrect 97 ms 19564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 20460 KB Output is correct
2 Incorrect 97 ms 19564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 20460 KB Output is correct
2 Incorrect 97 ms 19564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6636 KB Output is correct
2 Correct 53 ms 6636 KB Output is correct
3 Correct 51 ms 6508 KB Output is correct
4 Correct 51 ms 6636 KB Output is correct
5 Correct 44 ms 6508 KB Output is correct
6 Correct 48 ms 6892 KB Output is correct
7 Correct 51 ms 6892 KB Output is correct
8 Correct 42 ms 6380 KB Output is correct
9 Correct 47 ms 6380 KB Output is correct
10 Correct 47 ms 6764 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 14 ms 4588 KB Output is correct
13 Correct 13 ms 4716 KB Output is correct
14 Correct 15 ms 4588 KB Output is correct
15 Correct 16 ms 4716 KB Output is correct
16 Correct 14 ms 4588 KB Output is correct
17 Correct 13 ms 4588 KB Output is correct
18 Correct 14 ms 4716 KB Output is correct
19 Correct 13 ms 4588 KB Output is correct
20 Correct 0 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 640 KB Output is correct
23 Correct 19 ms 4588 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 20460 KB Output is correct
2 Incorrect 97 ms 19564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 20460 KB Output is correct
2 Incorrect 97 ms 19564 KB Output isn't correct
3 Halted 0 ms 0 KB -