oj.uz

Submission #416136

# Submission time Handle Problem Language Result Execution time Memory
416136 2021-06-02T05:06:02 Z DEQK Dreaming (IOI13_dreaming) C++17
18 / 100
 95 ms 19388 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 100100;
/*int travelTime(int n,int m,int l,vector<int> a,vector<int> b,vector<int> t) {
	
}*/
int n, m, l, ans;
int us[N], dp[N], was[N];
vector<pair<int, int>> g[N];
pair<int, int> best;
void dfs(int u) {
	us[u] = 1;
	for(auto to : g[u]) if(!us[to.first]) {
		dfs(to.first);
		dp[u] = max(dp[u], dp[to.first] + to.second);
	}
}
void dfs2(int u,int val) {
	was[u] = 1;
	vector<int> p, s;
	ans = max(ans, max(dp[u], val));
	if(best.first > max(dp[u], val)) {
		best = {max(dp[u], val), u};
	}
	for(int i = 0; i < g[u].size(); ++i) {
		int to = g[u][i].first, c = g[u][i].second;
		if(was[to]) continue;
		p.push_back(!p.empty() ? max(p.back(), dp[to] + c) : dp[to] + c);
	}
	for(int i = g[u].size() - 1; i >= 0; i--) {
		int to = g[u][i].first, c = g[u][i].second;
		if(was[to]) continue;
		s.push_back(s.empty() ? dp[to] + c : max(s.back(), dp[to] + c));
	}
	reverse(s.begin(), s.end());
	for(int i = g[u].size() - 1; i >= 0; i--) {
		int to = g[u][i].first, c = g[u][i].second;
		if(was[to]) continue;
		int f = val;
		if(i) f = max(f, p[i - 1] );
		if(i + 1 < s.size()) f = max(f, s[i + 1]);
		dfs2(to, f + c);
	}
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]) {
	for(int i = 0; i < m; ++i) {
		int u = a[i],v = b[i],w = t[i];
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}	
	vector<pair<int, int>> d;	
	for(int i = 0; i < n; ++i) {
		if(!us[i]) {
			dfs(i);
			best = {2e9, 0};
			dfs2(i, 0);
			d.push_back(best);
		}
	}
	sort(d.begin(), d.end(), [&] (pair<int, int> &x, pair<int, int> &y) {
		return x.first > y.first;
	});
	if(d.size() > 1) {
		ans = max(ans, d[0].first + d[1].first + l);
	}
	if(d.size() > 2) {
		ans = max(ans, d[1].first + d[2].first + 2 * l);
	}
	return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i = 0; i < g[u].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~
dreaming.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(i + 1 < s.size()) f = max(f, s[i + 1]);
      |      ~~~~~~^~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19388 KB Output is correct
2 Incorrect 95 ms 18492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19388 KB Output is correct
2 Incorrect 95 ms 18492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6676 KB Output is correct
2 Correct 32 ms 6680 KB Output is correct
3 Correct 36 ms 7048 KB Output is correct
4 Correct 34 ms 7068 KB Output is correct
5 Correct 51 ms 7016 KB Output is correct
6 Correct 42 ms 7844 KB Output is correct
7 Correct 30 ms 7252 KB Output is correct
8 Correct 34 ms 6980 KB Output is correct
9 Correct 33 ms 6972 KB Output is correct
10 Correct 36 ms 7236 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 8 ms 4860 KB Output is correct
13 Correct 8 ms 4836 KB Output is correct
14 Correct 8 ms 4828 KB Output is correct
15 Correct 8 ms 4804 KB Output is correct
16 Correct 8 ms 4804 KB Output is correct
17 Correct 8 ms 4548 KB Output is correct
18 Correct 8 ms 4932 KB Output is correct
19 Correct 8 ms 4804 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2656 KB Output is correct
22 Correct 2 ms 2764 KB Output is correct
23 Correct 8 ms 4804 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 19388 KB Output is correct
2 Incorrect 95 ms 18492 KB Output isn't correct
3 Halted 0 ms 0 KB -