oj.uz

Submission #940166

# Submission time Handle Problem Language Result Execution time Memory
940166 2024-03-07T06:18:36 Z vjudge1 Dreaming (IOI13_dreaming) C++17
18 / 100
 49 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 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});
 		}
	}
	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 = 1; 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 = 1; i <= n; i++) {
		if (i == get(i)) cnt++;
		if (i == get(i) && sz[i] > 1) s.push_back(calc(i, n));
	}
	return 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 Incorrect 49 ms 39896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 36444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 39896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 38736 KB Output is correct
2 Correct 37 ms 39332 KB Output is correct
3 Correct 33 ms 38736 KB Output is correct
4 Correct 31 ms 38744 KB Output is correct
5 Correct 32 ms 38740 KB Output is correct
6 Correct 33 ms 39248 KB Output is correct
7 Correct 32 ms 39004 KB Output is correct
8 Correct 31 ms 38748 KB Output is correct
9 Correct 32 ms 38736 KB Output is correct
10 Correct 35 ms 39248 KB Output is correct
11 Correct 9 ms 36444 KB Output is correct
12 Correct 10 ms 36444 KB Output is correct
13 Correct 9 ms 36444 KB Output is correct
14 Correct 9 ms 36444 KB Output is correct
15 Correct 9 ms 36444 KB Output is correct
16 Correct 9 ms 36444 KB Output is correct
17 Correct 9 ms 36496 KB Output is correct
18 Correct 10 ms 36444 KB Output is correct
19 Correct 9 ms 36444 KB Output is correct
20 Correct 10 ms 36444 KB Output is correct
21 Correct 8 ms 36444 KB Output is correct
22 Correct 9 ms 36444 KB Output is correct
23 Correct 9 ms 36444 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 36444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 39896 KB Output isn't correct
2 Halted 0 ms 0 KB -