oj.uz

Submission #787996

# Submission time Handle Problem Language Result Execution time Memory
787996 2023-07-19T15:55:53 Z allin27x Dreaming (IOI13_dreaming) C++17
18 / 100
 105 ms 43276 KB 
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"

int ds[2][(int)1e5];
unordered_map<int,int> adj[(int)1e5];
int vis[(int)1e5];
int ind = 0;
unordered_set<int> sets[(int)1e5];
int cp[(int)1e5];

void dfs(int i , int p, int len, int x){
	sets[ind].insert(i);
	vis[i] = 1;
	ds[x][i] = len;
	for (auto const &pair: adj[i]){
		int c = pair.first; int w= pair.second;
		if (c==p) continue;
		dfs(c,i, len+w,x);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	for (int i=0; i<M; i++){
		int a = A[i]; int b = B[i];
		adj[a][b] = T[i]; adj[b][a] = T[i];
	}
	int r;
	for (int i=0; i<N; i++){
		if (vis[i]) continue;
		dfs(i,i,0,0);
		int a1 = i;
		for (auto c: sets[ind]){
			if (ds[0][c]>ds[0][a1]) a1 = c;
		}
		dfs(a1,a1,0,0);
		int a2 = a1;
		r = a1;
		for (auto c: sets[ind]){
			if (ds[0][c]>ds[0][a2]) a2 = c;
		}
		dfs(a2,a2,0,1);
		int ans = 1e7;
		for (auto c: sets[ind]){
			ans = min(ans, max(ds[0][c], ds[1][c]));
		}
		cp[ind] = ans;
		ind++;
	}
	if (ind == 1){
		return ds[1][r];
	}
	sort(cp, cp+ind);
	if (ind ==2 ) return L + cp[ind-1] + cp[ind-2];
	return max(L + cp[ind-1] + cp[ind-2], 2*L + cp[ind-2] + cp[ind-3]);
}

// int main(){
// 	int n = 12; int m = 8 ;
// 	int l = 2;
// 	int a[] = {0, 8, 2, 5, 5, 1, 1, 10};
// 	int b[] = {8, 2, 7, 11, 1, 3, 9, 6};
// 	int t[] = {4, 2, 4, 3, 7, 1, 5, 3};
// 	cout<<travelTime(n,m,l,a,b,t);
// }

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:51:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   return ds[1][r];
      |                 ^

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 43276 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 51 ms 31648 KB Output is correct
2 Correct 48 ms 31644 KB Output is correct
3 Correct 45 ms 31500 KB Output is correct
4 Correct 46 ms 31504 KB Output is correct
5 Correct 51 ms 31436 KB Output is correct
6 Correct 56 ms 32772 KB Output is correct
7 Correct 48 ms 32428 KB Output is correct
8 Correct 51 ms 31192 KB Output is correct
9 Correct 53 ms 30964 KB Output is correct
10 Correct 52 ms 32196 KB Output is correct
11 Correct 6 ms 11264 KB Output is correct
12 Correct 26 ms 26964 KB Output is correct
13 Correct 25 ms 27020 KB Output is correct
14 Correct 24 ms 26936 KB Output is correct
15 Correct 27 ms 26988 KB Output is correct
16 Correct 25 ms 26848 KB Output is correct
17 Correct 26 ms 26892 KB Output is correct
18 Correct 25 ms 27012 KB Output is correct
19 Correct 26 ms 26964 KB Output is correct
20 Correct 6 ms 11208 KB Output is correct
21 Correct 6 ms 11220 KB Output is correct
22 Correct 7 ms 11776 KB Output is correct
23 Correct 24 ms 26876 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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