Submission #151768

#	Time	Username	Problem	Language	Result	Execution time	Memory
151768		abacaba	Dreaming (IOI13_dreaming)	C++14	18 / 100	175 ms	29164 KiB

dreaming

#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <math.h>
#include <random>
#include <string>
#include <cstring>
#include "dreaming.h"
#include <set>
#include <vector>
#include <map>
using namespace std;

#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], par[N];
vector <pii> g[N];
set <int> c, comp;
vector <int> f[N];
bool used[N];
queue <int> 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) {
	vector <int> path = {};
	used[componen] = true;
	for(int i : f[componen])
    	d[i] = -1;
	q.push(f[componen].back());
    d[q.front()] = 0;
	while(!q.empty()) {
    	int v = q.front();
    	q.pop();
    	for(pii to : g[v])
    		if(d[to.f] == -1) {
    			d[to.f] = d[v] + to.se;
    			q.push(to.f);
    		}
    }
    int ind = -1;
    for(int i : f[componen])
    	if(ind == -1 || d[i] > d[ind])
    		ind = i;
    for(int i : f[componen])
        if(i != ind)
        	d[i] = -1;
    q.push(ind);
    d[ind] = 0;
    while(!q.empty()) {
    	int v = q.front();
    	q.pop();
    	for(pii to : g[v])
    		if(d[to.f] == -1) {
    			par[to.f] = v;
    			d[to.f] = d[v] + to.se;
    			q.push(to.f);
    		}
    }

    int v = ind;

    ind = -1;
    for(int i : f[componen])
        if(ind == -1 || d[i] > d[ind])
            ind = i;

    for(; ind != v; ind = par[ind])
    	path.pb(ind);
    path.pb(v);
    center[componen] = path[path.size() / 2];

    for(int i : f[componen])
        d[i] = -1;
    q.push(center[componen]);
    d[q.front()] = 0;
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(pii to : g[v])
            if(d[to.f] == -1) {
                d[to.f] = d[v] + to.se;
                q.push(to.f);
            }
    }
    for(int i : f[componen])
        d[center[componen]] = max(d[center[componen]], d[i]);
    c.insert(center[componen]);
}
 
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 = 0; i < n; ++i)
        d[i] = -1;
    d[0] = 0;
    q.push(0);
    while(!q.empty()) {
    	int v = q.front();
    	q.pop();
    	for(pii to : g[v])
    		if(d[to.f] == -1) {
    			d[to.f] = d[v] + to.se;
    			q.push(to.f);
    		}
    }
    int ind = max_element(d, d + n) - d;
    for(int i = 0; i < n; ++i)
        d[i] = -1;
    d[ind] = 0;
    q.push(ind);
    while(!q.empty()) {
    	int v = q.front();
    	q.pop();
    	for(pii to : g[v])
    		if(d[to.f] == -1) {
    			d[to.f] = d[v] + to.se;
    			q.push(to.f);
    		}
    }
    return *max_element(d, d + n);
}

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