oj.uz

Submission #940193

# Submission time Handle Problem Language Result Execution time Memory
940193 2024-03-07T06:32:08 Z mansur Dreaming (IOI13_dreaming) C++17
18 / 100
 53 ms 39896 KB 
#include<bits/stdc++.h>	
#include "dreaming.h"
using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

const int inf = 1e9, N = 1e6;

int travelTime2(int n, int l, vector<int> s) {
	//cout << n << '\n';
	//for (int x: s) cout << x << ' ';
	//cout << '\n';
	if (n == 1) return 0;
	if (n == 2) {
		if (sz(s)) return s[0];
		return l;
	}
	s.push_back(0);
	s.push_back(0);
	s.push_back(0);
	sort(rall(s));
	return max(s[0] + s[1] + l, s[1] + s[2] + 2 * l);	     	
}

vector<int> d0(N, inf), d1(N, inf);
vector<pii> g[N];
int val;

int calc(int x, int n) {
	set<pii> s;
	vector<int> h;
	d0[x] = 0;
	s.insert({0, x});
	int a = x;
	while (sz(s)) {
		x = (*s.begin()).s;
		if (d0[x] > d0[a]) a = x;
		h.push_back(x);
		s.erase(s.begin());
		for (auto [to, w]: g[x]) {
			if (d0[to] < d0[x] + w) continue;
			s.erase({d0[to], to});
			d0[to] = d0[x] + w;
			s.insert({d0[to], to});
 		}
	}
	d1[a] = 0;
	s.insert({0, a});
	int b = a;
	while (sz(s)) {
		x = (*s.begin()).s;
		if (d1[x] > d1[b]) b = x;
		s.erase(s.begin());
		for (auto [to, w]: g[x]) {
			if (d1[to] < d1[x] + w) continue;
			s.erase({d1[to], to});
			d1[to] = d1[x] + w;
			s.insert({d1[to], to});
 		}
	}
	val = max(val, d1[b]);
	for (int v: h) d0[v] = inf;
	d0[b] = 0;
	s.insert({0, b});
	while (sz(s)) {
		x = (*s.begin()).s;
		s.erase(s.begin());
		for (auto [to, w]: g[x]) {
			if (d0[to] < d0[x] + w) continue;
			s.erase({d0[to], to});
			d0[to] = d0[x] + w;
			s.insert({d0[to], to});
 		}
	}
	int ans = inf;
	for (int v: h) {
		x = max(d0[v], d1[v]);
		ans = min(ans, x);
		d0[v] = d1[v] = inf;
	}
	return ans;
}

int p[N], sz[N];

int get(int x) {
	if (p[x] == x) return x;
	return p[x] = get(p[x]);
}

void unite(int a, int b) {
	a = get(a), b = get(b);
	if (a == b) return;
	if (sz[a] > sz[b]) swap(a, b);
	p[a] = b;
	sz[b] += sz[a];
}

int travelTime(int n, int m, int l, int a[], int b[], int c[]) {    
	for (int i = 0; i < n; i++) p[i] = i, sz[i] = 1;
	for (int i = 0; i < m; i++) {
		g[a[i]].push_back({b[i], c[i]});
		g[b[i]].push_back({a[i], c[i]});
		unite(a[i], b[i]);
	}
	vector<int> s;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (i == get(i)) cnt++;
		if (i == get(i) && sz[i] > 1) s.push_back(calc(i, n)), cnt++;
	}
	return max(val, travelTime2(cnt, l, s));
}

#ifdef M
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int n, m, l;
	cin >> n >> m >> l;
	int a[m], b[m], c[m];
	for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i];
	cout << travelTime(n, m, l, a, b, c);
}
#endif

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 39896 KB Output is correct
2 Correct 50 ms 39892 KB Output is correct
3 Correct 41 ms 38860 KB Output is correct
4 Correct 15 ms 36956 KB Output is correct
5 Correct 16 ms 36712 KB Output is correct
6 Correct 19 ms 37212 KB Output is correct
7 Incorrect 9 ms 36444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36444 KB Output is correct
2 Correct 9 ms 36444 KB Output is correct
3 Incorrect 10 ms 36440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 39896 KB Output is correct
2 Correct 50 ms 39892 KB Output is correct
3 Correct 41 ms 38860 KB Output is correct
4 Correct 15 ms 36956 KB Output is correct
5 Correct 16 ms 36712 KB Output is correct
6 Correct 19 ms 37212 KB Output is correct
7 Incorrect 9 ms 36444 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 32 ms 38748 KB Output is correct
2 Correct 32 ms 38816 KB Output is correct
3 Correct 31 ms 38748 KB Output is correct
4 Correct 34 ms 38740 KB Output is correct
5 Correct 33 ms 38748 KB Output is correct
6 Correct 39 ms 38996 KB Output is correct
7 Correct 47 ms 39128 KB Output is correct
8 Correct 44 ms 38740 KB Output is correct
9 Correct 46 ms 38740 KB Output is correct
10 Correct 36 ms 38992 KB Output is correct
11 Correct 8 ms 36444 KB Output is correct
12 Correct 10 ms 36480 KB Output is correct
13 Correct 9 ms 36440 KB Output is correct
14 Correct 9 ms 36444 KB Output is correct
15 Correct 12 ms 36444 KB Output is correct
16 Correct 9 ms 36440 KB Output is correct
17 Correct 9 ms 36444 KB Output is correct
18 Correct 10 ms 36432 KB Output is correct
19 Correct 9 ms 36440 KB Output is correct
20 Correct 9 ms 36440 KB Output is correct
21 Correct 10 ms 36440 KB Output is correct
22 Correct 9 ms 36444 KB Output is correct
23 Correct 12 ms 36444 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36444 KB Output is correct
2 Correct 9 ms 36444 KB Output is correct
3 Incorrect 10 ms 36440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 39896 KB Output is correct
2 Correct 50 ms 39892 KB Output is correct
3 Correct 41 ms 38860 KB Output is correct
4 Correct 15 ms 36956 KB Output is correct
5 Correct 16 ms 36712 KB Output is correct
6 Correct 19 ms 37212 KB Output is correct
7 Incorrect 9 ms 36444 KB Output isn't correct
8 Halted 0 ms 0 KB -