Submission #336622

#	Time	Username	Problem	Language	Result	Execution time	Memory
336622		arwaeystoamneg	Dreaming (IOI13_dreaming)	C++17	18 / 100	97 ms	20460 KiB

dreaming

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23