Submission #69850

#	Time	Username	Problem	Language	Result	Execution time	Memory
69850		FLDutchman	Dreaming (IOI13_dreaming)	C++14	100 / 100	123 ms	15580 KiB

dreaming

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

#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define V vector

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;


const int NMAX = 1e5+10;

struct edge{
	int v, l;
};

int N, M;
V<V<edge>> adj;
bitset<NMAX> vis;

void flood(int u){
	vis[u] = 1;
	for(auto &e : adj[u]) if(!vis[e.v]) flood(e.v); 
}


ii furthest(int u, int p){
	//cout << "Furthest " << u << " " << p << endl;
	ii far = {0, u};
	for(edge &e : adj[u]) if(e.v != p) {
		ii t = furthest(e.v, u);
		t.fst += e.l;
		//cout << "cand " << t.fst << " " << t.snd;
		far = max(far, t);
	}
	return far;
}

vi path;
int printpath(int u, int goal, int p, int d = 0){
	//cout << u << " " << goal << " " << p << " " << d << endl;
	if(u == goal) {path.pb(d); return 1;}
	for(auto &e : adj[u]) if(e.v != p) {
		if(printpath(e.v, goal, u, d+e.l)) {
			path.pb(d);
			return 1;
		}
	}
	return 0;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    if(n == 1) return 0;
    vis.reset();
    N = n;
    M = m;
    adj.resize(N);
    FOR(i, 0, M) {
    	adj[A[i]].pb({B[i], T[i]});
    	adj[B[i]].pb({A[i], T[i]});
    }
    vi diams;
    vi radii;
    //cout<<N<<endl;
    //FOR(i, 0, N) cout << vis[i] << endl;
    FOR(i, 0, N) if(!vis[i]) {
    	//cout<<i<<endl;
    	ii p1 = furthest(i, -1);
    	ii p2 = furthest(p1.snd, -1);
    	diams.pb(p2.fst);
    	//cout << p1.snd << " " << p2.snd << endl;
    	path.clear();
    	printpath(p1.snd, p2.snd, -1);
    	int r = 2e9;

    	for(int k : path) r = min(r, max(k, p2.fst - k));
    	radii.pb(r);
    	flood(i);
    }
    //for (int d : diams) cout << d << " ";
    //cout << endl;
    //cout << radii.size() << endl;
    sort(radii.begin(), radii.end());
    radii[radii.size()-1] -= L;
    sort(radii.begin(), radii.end());
    //for(int r :radii) cout << r << endl;
    int best = radii.back() + radii[radii.size()-2] + 2*L;
    for(int d : diams) best = max(d, best);
    return best;
}

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