oj.uz

Submission #940201

# Submission time Handle Problem Language Result Execution time Memory
940201 2024-03-07T06:35:05 Z mansur Dreaming (IOI13_dreaming) C++17
18 / 100
 52 ms 40104 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 50 ms 40104 KB Output is correct
2 Correct 52 ms 39888 KB Output is correct
3 Correct 36 ms 38792 KB Output is correct
4 Correct 14 ms 36956 KB Output is correct
5 Correct 15 ms 36748 KB Output is correct
6 Correct 19 ms 37212 KB Output is correct
7 Incorrect 11 ms 36484 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 12 ms 36444 KB Output is correct
3 Incorrect 10 ms 36444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 40104 KB Output is correct
2 Correct 52 ms 39888 KB Output is correct
3 Correct 36 ms 38792 KB Output is correct
4 Correct 14 ms 36956 KB Output is correct
5 Correct 15 ms 36748 KB Output is correct
6 Correct 19 ms 37212 KB Output is correct
7 Incorrect 11 ms 36484 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 34 ms 38748 KB Output is correct
2 Correct 38 ms 38932 KB Output is correct
3 Correct 35 ms 38772 KB Output is correct
4 Correct 40 ms 38884 KB Output is correct
5 Correct 33 ms 38784 KB Output is correct
6 Correct 34 ms 39004 KB Output is correct
7 Correct 32 ms 38992 KB Output is correct
8 Correct 31 ms 38740 KB Output is correct
9 Correct 35 ms 38752 KB Output is correct
10 Correct 34 ms 38992 KB Output is correct
11 Correct 9 ms 36444 KB Output is correct
12 Correct 11 ms 36516 KB Output is correct
13 Correct 10 ms 36440 KB Output is correct
14 Correct 12 ms 36444 KB Output is correct
15 Correct 10 ms 36444 KB Output is correct
16 Correct 9 ms 36316 KB Output is correct
17 Correct 11 ms 36440 KB Output is correct
18 Correct 10 ms 36444 KB Output is correct
19 Correct 10 ms 36464 KB Output is correct
20 Correct 10 ms 36496 KB Output is correct
21 Correct 9 ms 36444 KB Output is correct
22 Correct 9 ms 36452 KB Output is correct
23 Correct 11 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 12 ms 36444 KB Output is correct
3 Incorrect 10 ms 36444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 40104 KB Output is correct
2 Correct 52 ms 39888 KB Output is correct
3 Correct 36 ms 38792 KB Output is correct
4 Correct 14 ms 36956 KB Output is correct
5 Correct 15 ms 36748 KB Output is correct
6 Correct 19 ms 37212 KB Output is correct
7 Incorrect 11 ms 36484 KB Output isn't correct
8 Halted 0 ms 0 KB -