Submission #151775

#	Time	Username	Problem	Language	Result	Execution time	Memory
151775		abacaba	Dreaming (IOI13_dreaming)	C++14	100 / 100	182 ms	24040 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], val[N];
vector <pii> g[N];
set <int> c, comp;
vector <int> f[N];
int 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];
	}
}
 
int bfs(int s, int mark) {
    q.push(s);
    int ind = s;
    used[s] = mark;
    d[s] = 0;
    while(!q.empty()) {
        int v = q.front();
        if(d[v] > d[ind])
            ind = v;
        q.pop();
        for(pii to : g[v])
            if(used[to.f] != mark) {
                used[to.f] = mark;
                d[to.f] = d[v] + to.se;
                q.push(to.f);
            }
    }
    return ind;
}
 
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]));
    	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) {
    	int x = bfs(f[i].back(), 1);
        int y = bfs(x, 2);
        int s = d[y], f = d[y], c = y;
        while(d[y] > 0) {
            for(pii to : g[y])
                if(d[to.f] == d[y] - to.se) {
                    y = to.f;
                    break;
                }
            int val = max(d[y], f - d[y]);
            if(val < s) {
                s = val;
                c = y;
            }
        }
        if(val[maxdiam] < s) {
            val[c] = s;
            maxdiam = c;
        }
        center[find(x)] = c;
    }
    for(int i : comp) {
    	if(find(maxdiam) == i)
    		continue;
    	g[maxdiam].pb(mp(center[i], l));
    	g[center[i]].pb(mp(maxdiam, l));
    }
    bfs(bfs(0, 1), 2);
    return *max_element(d, d + n);
}

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