oj.uz

Submission #279892

# Submission time Handle Problem Language Result Execution time Memory
279892 2020-08-22T11:54:18 Z amoo_safar Dreaming (IOI13_dreaming) C++17
18 / 100
 65 ms 12660 KB 
#include "dreaming.h"

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int N = 1e5 + 10;

int mk[N], fr[N], to[N], w[N];
vector<int> G[N], vis;

int dp[N], dp2[N];

void DFS(int u){
	mk[u] = 1;
	vis.pb(u);
	int adj;
	for(auto e : G[u]){
		adj = to[e] ^ fr[e] ^ u;
		if(!mk[adj]){
			DFS(adj);
			dp[u] = max(dp[u], dp[adj] + w[e]);
		}
	}
}
void DFS2(int u, int p){
	int adj, res = dp2[u];
	for(auto e : G[u]){
		adj = to[e] ^ fr[e] ^ u;
		if(adj == p) continue;
		dp2[adj] = max(res + w[e], dp2[adj]);
		res = max(res, dp[adj] + w[e]);
	}
	reverse(G[u].begin(), G[u].end());
	res = dp2[u];
	for(auto e : G[u]){
		adj = to[e] ^ fr[e] ^ u;
		if(adj == p) continue;
		dp2[adj] = max(res + w[e], dp2[adj]);
		res = max(res, dp[adj] + w[e]);
		DFS2(adj, u);
	}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < m; i++){
    	fr[i] = A[i];
    	to[i] = B[i];
    	G[A[i]].pb(i);
    	G[B[i]].pb(i);
    	w[i] = T[i];
    }
    vector<int> V;
    for(int i = 0; i < n; i++){
    	if(mk[i]) continue;
    	vis.clear();
    	DFS(i);
    	DFS2(i, -1);
    	int res = 2000000000;
    	for(auto x : vis) res = min(res, max(dp[x], dp2[x]));
    	V.pb(res);
    }
    sort(V.begin(), V.end());
    reverse(V.begin(), V.end());
    int ans = V[0];
    if(V.size() >= 2) ans = max(ans, L + V[0] + V[1]);
    if(V.size() >= 3) ans = max(ans, L + L + V[1] + V[2]);
    return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 12660 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 36 ms 7036 KB Output is correct
2 Correct 29 ms 7040 KB Output is correct
3 Correct 32 ms 7040 KB Output is correct
4 Correct 31 ms 7040 KB Output is correct
5 Correct 29 ms 7040 KB Output is correct
6 Correct 31 ms 7544 KB Output is correct
7 Correct 30 ms 7296 KB Output is correct
8 Correct 28 ms 7040 KB Output is correct
9 Correct 28 ms 6908 KB Output is correct
10 Correct 30 ms 7272 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 6 ms 4348 KB Output is correct
13 Correct 8 ms 4348 KB Output is correct
14 Correct 6 ms 4348 KB Output is correct
15 Correct 6 ms 4348 KB Output is correct
16 Correct 6 ms 4220 KB Output is correct
17 Correct 7 ms 3964 KB Output is correct
18 Correct 7 ms 4476 KB Output is correct
19 Correct 6 ms 4348 KB Output is correct
20 Correct 3 ms 2688 KB Output is correct
21 Correct 2 ms 2688 KB Output is correct
22 Correct 3 ms 2816 KB Output is correct
23 Correct 6 ms 4348 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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