Submission #151029

#	Time	Username	Problem	Language	Result	Execution time	Memory
151029		abacaba	Dreaming (IOI13_dreaming)	C++14	0 / 100	242 ms	28272 KiB

dreaming

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include "dreaming.h"
#include <algorithm>
#include <math.h>
#include <random>
#include <string>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <time.h>
using namespace __gnu_pbds;
using namespace std;

typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int inf = 2e9;
const int N = 2e5 + 15;
int n, m, l, maxdiam, sz[N], d[N], center[N], deg[N], p[N];
vector <pii> g[N];
set <int> c, comp;
vector <int> f[N];
bool used[N];
set <pii> q;

int find(int v) {
	if(v == p[v])
		return v;
	return p[v] = find(p[v]);
}

void unio(int a, int b) {
	a = find(a);
	b = find(b);
	if(a != b) {
		if(sz[a] < sz[b])
			swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
}

void bfs(int componen) {
	used[componen] = true;
	int maxlevel = 0;
	for(auto i : f[componen])
		if(deg[i] == 1) {
			--deg[i];
			q.insert(mp(0, i));
		}
	while(!q.empty()) {
		int v = q.begin()->se;
		q.erase(q.begin());
		for(pii to : g[v]) {
			--deg[to.f];
			if(deg[to.f] == 1) {
				d[to.f] = d[v] + to.se;
				q.insert(mp(-d[to.f], d[to.f]));
				maxlevel = max(maxlevel, d[to.f]);
			}
		}
	}
	for(int i : f[componen])
		if(d[i] == maxlevel) {
			c.insert(i);
			center[componen] = i;
		}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N, m = M, l = L;
	for(int i = 0; i < n; ++i)
		p[i] = i, sz[i] = 1;
    for(int i = 0; i < m; ++i) {
    	g[A[i]].pb(mp(B[i], T[i]));
    	g[B[i]].pb(mp(A[i], T[i]));
    	deg[A[i]]++, deg[B[i]]++;
    	unio(A[i], B[i]);
    }
    for(int i = 0; i < n; ++i) {
    	comp.insert(find(i));
    	f[find(i)].pb(i);
    }
    for(int i : comp)
    	if(!used[i])
	    	bfs(i);
    for(int i : c)
    	if(d[i] > d[maxdiam])
    		maxdiam = i;
    for(int i : comp) {
    	if(find(maxdiam) == i)
    		continue;
    	g[maxdiam].pb(mp(center[i], l));
    	g[center[i]].pb(mp(maxdiam, l));
    }
    for(int i = 1; i < n; ++i)
    	d[i] = inf;
    q.insert(mp(0, 0));
    int maxlevel = 0;
    while(!q.empty()) {
    	int v = q.begin()->se;
    	maxlevel = max(maxlevel, d[v]);
    	q.erase(q.begin());
    	for(pii to : g[v]) {
    		if(d[to.f] > d[v] + to.se) {
    			q.erase(mp(d[to.f], to.f));
    			d[to.f] = d[v] + to.se;
    			q.insert(mp(d[to.f], to.f));
    		}
    	}
    }
    for(int i = 0; i < n; ++i)
    	if(d[i] == maxlevel) {
    		q.insert(mp(0, i));
    		d[i] = 0;
    		for(int j = 0; j < n; ++j)
    			if(j != i)
    				d[j] = inf;
    		int maxx = 0;
    		while(!q.empty()) {
    			int v = q.begin()->se;
    			maxx = max(maxx, q.begin()->f);
    			q.erase(q.begin());
    			for(pii to : g[v]) {
    				if(d[to.f] > d[v] + to.se) {
    					q.erase(mp(d[to.f], to.f));
    					d[to.f] = d[v] + to.se;
    					q.insert(mp(d[to.f], to.f));
    				}
    			}
    		}
    		return maxx;
    	}
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:157:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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