oj.uz

Submission #151768

# Submission time Handle Problem Language Result Execution time Memory
151768 2019-09-04T15:32:21 Z abacaba Dreaming (IOI13_dreaming) C++14
18 / 100
 175 ms 29164 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 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.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17780 KB Output is correct
2 Correct 123 ms 17848 KB Output is correct
3 Correct 74 ms 15084 KB Output is correct
4 Correct 22 ms 11000 KB Output is correct
5 Correct 21 ms 10704 KB Output is correct
6 Correct 32 ms 11720 KB Output is correct
7 Incorrect 11 ms 9720 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17780 KB Output is correct
2 Correct 123 ms 17848 KB Output is correct
3 Correct 74 ms 15084 KB Output is correct
4 Correct 22 ms 11000 KB Output is correct
5 Correct 21 ms 10704 KB Output is correct
6 Correct 32 ms 11720 KB Output is correct
7 Incorrect 11 ms 9720 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17780 KB Output is correct
2 Correct 123 ms 17848 KB Output is correct
3 Correct 74 ms 15084 KB Output is correct
4 Correct 22 ms 11000 KB Output is correct
5 Correct 21 ms 10704 KB Output is correct
6 Correct 32 ms 11720 KB Output is correct
7 Incorrect 11 ms 9720 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 156 ms 24300 KB Output is correct
2 Correct 160 ms 24592 KB Output is correct
3 Correct 153 ms 24304 KB Output is correct
4 Correct 175 ms 24596 KB Output is correct
5 Correct 159 ms 24388 KB Output is correct
6 Correct 168 ms 25452 KB Output is correct
7 Correct 162 ms 24964 KB Output is correct
8 Correct 155 ms 24156 KB Output is correct
9 Correct 146 ms 23920 KB Output is correct
10 Correct 160 ms 24968 KB Output is correct
11 Correct 11 ms 9848 KB Output is correct
12 Correct 92 ms 29024 KB Output is correct
13 Correct 90 ms 28908 KB Output is correct
14 Correct 92 ms 29164 KB Output is correct
15 Correct 92 ms 29032 KB Output is correct
16 Correct 91 ms 28904 KB Output is correct
17 Correct 97 ms 28652 KB Output is correct
18 Correct 91 ms 29036 KB Output is correct
19 Correct 93 ms 28992 KB Output is correct
20 Correct 11 ms 9848 KB Output is correct
21 Correct 11 ms 9720 KB Output is correct
22 Correct 13 ms 10364 KB Output is correct
23 Correct 91 ms 28904 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17780 KB Output is correct
2 Correct 123 ms 17848 KB Output is correct
3 Correct 74 ms 15084 KB Output is correct
4 Correct 22 ms 11000 KB Output is correct
5 Correct 21 ms 10704 KB Output is correct
6 Correct 32 ms 11720 KB Output is correct
7 Incorrect 11 ms 9720 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 17780 KB Output is correct
2 Correct 123 ms 17848 KB Output is correct
3 Correct 74 ms 15084 KB Output is correct
4 Correct 22 ms 11000 KB Output is correct
5 Correct 21 ms 10704 KB Output is correct
6 Correct 32 ms 11720 KB Output is correct
7 Incorrect 11 ms 9720 KB Output isn't correct
8 Halted 0 ms 0 KB -