Submission #1275149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275149		KluydQ	꿈 (IOI13_dreaming)	C++20	18 / 100	67 ms	27548 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

//#define respagold ios_base::sync_with_stdio(0), cin.tie(0);     
//#define int long long
#define ll long long
#define int2 __int128_t
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back
#define pf push_front
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define pii pair <int, int>
#define ppi pair <pair <int, int>, int>
#define pip pair <int, pair <int, int>>
#define mkp make_pair
 
using namespace std;

const int N = 2e5 + 12;
const int inf = 2e9;
const int mod = 1e9 + 7;
const double eps = 1e-20;

int n, m, l, x, y, w, mn, mxd, d[N], used[N];
vector <pii> g[N]; vector <int> ve;
multiset <int> st[N];

void dfs( int v, int p = 0 )
{
	for( auto to : g[v] )
	{
		if( to.F != p )
		{
			dfs( to.F, v ); st[v].ins(d[to.F] + to.S);
			d[v] = max(d[v], d[to.F] + to.S);
		}
	}
	ve.pb(v);
}
void dfs2( int v, int p = 0, int up = 0 )
{
	mn = min(mn, max(d[v], up));
	
	for( auto to : g[v] )
	{
		if( to.F != p )
		{
			st[v].erase(st[v].find(d[to.F] + to.S)); int nw = up;
			if(!st[v].empty()) nw = max(nw, *st[v].rbegin());
			st[v].ins(d[to.F] + to.S);
			
			dfs2(to.F, v, nw + to.S);
		}
	}
	used[v] = 1;
}
int dist( int v, int p = 0 )
{
	dfs(v);
	int mx = -inf, id;
	
	for( auto i : ve )
	{
		if( d[i] > mx ) mx = d[i], id = i;
		d[i] = 0, st[i].clear();
	}
	ve.clear(), dfs(id);
	
	for( auto i : ve )
	{
		if( d[i] > mx ) mx = d[i];
		d[i] = 0, st[i].clear();
	}
	ve.clear();
	return mx;
}
int travelTime( int N, int M, int L, int A[], int B[], int T[] )
{
	n = N, m = M, l = L;
	
	FOR( i, 0, m - 1, 1 )
	{
		x = A[i], y = B[i], w = T[i];
		x ++, y ++;
		
		g[x].pb({y, w});
		g[y].pb({x, w});
	}
	vector <int> vals;
	
	FOR( i, 1, n, 1 )
	{
		if( !used[i] )
		{
			mxd = max(mxd, dist(i));
			
			mn = inf;
			dfs(i), dfs2(i);
			vals.pb(mn);
		}
	}
	sort( all(vals) );
	reverse( all(vals) );
	
	if( sz(vals) == 1 ) return mxd;
	else if( sz(vals) == 2 ) return max(mxd, vals[0] + vals[1] + l);
	else return max({ mxd, vals[0] + vals[1] + l, vals[1] + vals[2] + 2 * l });
}
/*
signed main()
{
	//respagold
	
	int test = 1;
	if( !test ) cin >> test;
	while( test -- ) solve();
}*/

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23