oj.uz

Submission #336621

# Submission time Handle Problem Language Result Execution time Memory
336621 2020-12-16T03:21:17 Z arwaeystoamneg Dreaming (IOI13_dreaming) C++17
18 / 100
 107 ms 21740 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,size[0] + size[1] + l, size[1] + size[2] + 2 * l });
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21740 KB Output is correct
2 Incorrect 104 ms 20716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21740 KB Output is correct
2 Incorrect 104 ms 20716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21740 KB Output is correct
2 Incorrect 104 ms 20716 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 44 ms 7020 KB Output is correct
2 Correct 50 ms 7020 KB Output is correct
3 Correct 48 ms 7020 KB Output is correct
4 Correct 50 ms 6980 KB Output is correct
5 Correct 52 ms 7020 KB Output is correct
6 Correct 49 ms 7404 KB Output is correct
7 Correct 47 ms 7276 KB Output is correct
8 Correct 44 ms 6892 KB Output is correct
9 Correct 45 ms 6784 KB Output is correct
10 Correct 47 ms 7276 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 14 ms 4716 KB Output is correct
13 Correct 14 ms 4716 KB Output is correct
14 Correct 14 ms 4588 KB Output is correct
15 Correct 14 ms 4716 KB Output is correct
16 Correct 14 ms 4588 KB Output is correct
17 Correct 13 ms 4608 KB Output is correct
18 Correct 14 ms 4716 KB Output is correct
19 Correct 14 ms 4588 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 14 ms 4588 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21740 KB Output is correct
2 Incorrect 104 ms 20716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21740 KB Output is correct
2 Incorrect 104 ms 20716 KB Output isn't correct
3 Halted 0 ms 0 KB -