Submission #282258

#	Time	Username	Problem	Language	Result	Execution time	Memory
282258		Ccucumber12	Dreaming (IOI13_dreaming)	C++17	100 / 100	152 ms	35604 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

#define F first
#define S second
#define siz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define EB emplace_back
#define MP make_pair
#define PF push_front
#define PB push_back
#define POB pop_back
#define POF pop_front
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define kiyohime ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'
#define debug(...) cerr<<#__VA_ARGS__<<" = ";dbg(__VA_ARGS__);

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using vec = vector<T>;
template<typename T> using Prior = priority_queue<T>;
template<typename T> using prior = priority_queue<T, vec<T>, greater<T>>;

const int INF = 1e9 + 1;
const ll LLINF = (ll)4*1e18;
const ll MOD = 1e9+7;
const double PI  = 3.14159265358;
const double EPS = 1e-8;
const int xx[8] = {0,1,0,-1,1,1,-1,-1};
const int yy[8] = {1,0,-1,0,1,-1,-1,1};

template<typename T> void dbg(T x){ cerr<<x<<endl; }
template<typename T, typename ...A> void dbg(T x, A ...y){ cerr<<x<<", "; dbg(y...);}

template <typename T>
void printv(vec<T> v, char c = ' ') {
    bool spc = false;
    for(auto i:v)
        if(spc) cout << c << i;
        else    cout << i, spc = true;
    cout << endl;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> void amax(T &a, T b) {if(a < b) a = b;}
template<typename T> void amin(T &a, T b) {if(a > b) a = b;}
void pmod(ll &a, ll b) {a = (a+b)%MOD;}
void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;}
void tmod(ll &a, ll b) {a = (a*b)%MOD;}
void UNI(vec<int> &v) {sort(ALL(v)); v.rs(unique(ALL(v))-v.begin());}
int getint() {int ret; cin >> ret; return ret;}
ll POW(ll a, ll b) {ll res=1; do{if(b%2)tmod(res,a);tmod(a,a);}while(b>>=1); return res;}
ll getll() {ll ret; cin >> ret; return ret;}

const int MXN = 1000000;
const int N = MXN + 10;

vec<pii> g[N];
int vis[N], par[N], dep[N];
int dis, pt;

void dfs(int x, int p, int v){
	par[x] = p;
	dep[x] = v;
	vis[x] = true;
	for(auto i:g[x]) if(i.F != p)
		dfs(i.F, x, v + i.S);
	if(v > dis) pt = x;
	amax(dis, v);
}


int travelTime(int n, int m, int l, int a[], int b[], int t[]){
	rep(i, m){
		g[a[i]].EB(b[i], t[i]);
		g[b[i]].EB(a[i], t[i]);
	}
	
	vec<int> v;
	int self = 0;
	rep(i, n) if(!vis[i]){
		dis = pt = -1;
		dfs(i, -1, 0);
		
		dis = -1;
		dfs(pt, -1, 0);
		
		int idx = pt, len = INF;
		while(~idx) {
			amin(len, max(dep[idx], dis - dep[idx]));
			idx = par[idx];
		}
		v.EB(len);
		amax(self, dis);
	}
	
	sort(ALL(v), greater<int>());
	if(siz(v) == 1)
		return self;
	else if(siz(v) == 2)
		return max(self, v[0] + v[1] + l);
	else
		return max({self, v[0] + v[1] + l, v[1] + v[2] + 2*l}); 
}

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