oj.uz

Submission #788016

# Submission time Handle Problem Language Result Execution time Memory
788016 2023-07-19T16:15:07 Z allin27x Dreaming (IOI13_dreaming) C++17
18 / 100
 143 ms 44532 KB 
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#define int long long

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);
	}
}

signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed 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++) vis[i] = 0;
	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 + max(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:53:17: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |   return ds[1][r];
      |          ~~~~~~~^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 44532 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 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 143 ms 44532 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 73 ms 33232 KB Output is correct
2 Correct 62 ms 33224 KB Output is correct
3 Correct 61 ms 33044 KB Output is correct
4 Correct 57 ms 33240 KB Output is correct
5 Correct 61 ms 32972 KB Output is correct
6 Correct 62 ms 34376 KB Output is correct
7 Correct 60 ms 34188 KB Output is correct
8 Correct 56 ms 32652 KB Output is correct
9 Correct 71 ms 32728 KB Output is correct
10 Correct 63 ms 33880 KB Output is correct
11 Correct 6 ms 11220 KB Output is correct
12 Correct 31 ms 28500 KB Output is correct
13 Correct 32 ms 28492 KB Output is correct
14 Correct 32 ms 28424 KB Output is correct
15 Correct 32 ms 28444 KB Output is correct
16 Correct 31 ms 28476 KB Output is correct
17 Correct 31 ms 28444 KB Output is correct
18 Correct 33 ms 28560 KB Output is correct
19 Correct 31 ms 28492 KB Output is correct
20 Correct 7 ms 11284 KB Output is correct
21 Correct 6 ms 11280 KB Output is correct
22 Correct 8 ms 11796 KB Output is correct
23 Correct 32 ms 28440 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 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 143 ms 44532 KB Output isn't correct
2 Halted 0 ms 0 KB -