oj.uz

Submission #151769

# Submission time Handle Problem Language Result Execution time Memory
151769 2019-09-04T15:39:36 Z abacaba Dreaming (IOI13_dreaming) C++14
18 / 100
 200 ms 29064 KB 
#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 dfs(int v, int p = -1) {
    par[v] = p;
    for(pii to : g[v]) {
        if(to.f != p) {
            d[to.f] = d[v] + to.se;
            dfs(to.f, v);
        }
    }
}
 
void bfs(int componen) {
	vector <int> path = {};
	used[componen] = true;

	for(int i : f[componen])
    	d[i] = 0;
    dfs(f[componen].back());

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

    for(int i : f[componen])
        d[i] = 0;
    dfs(ind);

    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] = 0;
    dfs(center[componen]);

    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));
    }
    memset(d, 0, sizeof(d));
    dfs(0);

    int ind = -1;
    for(int i = 0; i < n; ++i)
        if(ind == -1 || d[i] > d[ind])
            ind = i;

    memset(d, 0, sizeof(d));
    dfs(ind);

    return *max_element(d, d + n);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22260 KB Output is correct
2 Correct 100 ms 22136 KB Output is correct
3 Correct 63 ms 18184 KB Output is correct
4 Correct 22 ms 12280 KB Output is correct
5 Correct 21 ms 11612 KB Output is correct
6 Correct 31 ms 13284 KB Output is correct
7 Incorrect 12 ms 10616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22260 KB Output is correct
2 Correct 100 ms 22136 KB Output is correct
3 Correct 63 ms 18184 KB Output is correct
4 Correct 22 ms 12280 KB Output is correct
5 Correct 21 ms 11612 KB Output is correct
6 Correct 31 ms 13284 KB Output is correct
7 Incorrect 12 ms 10616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22260 KB Output is correct
2 Correct 100 ms 22136 KB Output is correct
3 Correct 63 ms 18184 KB Output is correct
4 Correct 22 ms 12280 KB Output is correct
5 Correct 21 ms 11612 KB Output is correct
6 Correct 31 ms 13284 KB Output is correct
7 Incorrect 12 ms 10616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 24516 KB Output is correct
2 Correct 152 ms 24552 KB Output is correct
3 Correct 153 ms 24460 KB Output is correct
4 Correct 150 ms 24692 KB Output is correct
5 Correct 164 ms 24480 KB Output is correct
6 Correct 200 ms 25484 KB Output is correct
7 Correct 160 ms 25128 KB Output is correct
8 Correct 147 ms 24256 KB Output is correct
9 Correct 153 ms 24208 KB Output is correct
10 Correct 153 ms 25032 KB Output is correct
11 Correct 12 ms 10488 KB Output is correct
12 Correct 93 ms 29036 KB Output is correct
13 Correct 94 ms 28996 KB Output is correct
14 Correct 93 ms 28976 KB Output is correct
15 Correct 91 ms 29032 KB Output is correct
16 Correct 90 ms 29032 KB Output is correct
17 Correct 95 ms 28904 KB Output is correct
18 Correct 90 ms 28908 KB Output is correct
19 Correct 90 ms 29064 KB Output is correct
20 Correct 12 ms 10616 KB Output is correct
21 Correct 11 ms 10488 KB Output is correct
22 Correct 13 ms 11128 KB Output is correct
23 Correct 88 ms 29032 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22260 KB Output is correct
2 Correct 100 ms 22136 KB Output is correct
3 Correct 63 ms 18184 KB Output is correct
4 Correct 22 ms 12280 KB Output is correct
5 Correct 21 ms 11612 KB Output is correct
6 Correct 31 ms 13284 KB Output is correct
7 Incorrect 12 ms 10616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 22260 KB Output is correct
2 Correct 100 ms 22136 KB Output is correct
3 Correct 63 ms 18184 KB Output is correct
4 Correct 22 ms 12280 KB Output is correct
5 Correct 21 ms 11612 KB Output is correct
6 Correct 31 ms 13284 KB Output is correct
7 Incorrect 12 ms 10616 KB Output isn't correct
8 Halted 0 ms 0 KB -