#include <stdio.h>
#include <vector>
#include "dreaming.h"
#define MAX_N 100001
#define oo (1<<30)
using namespace std;
vector< pair<int,int> > E[MAX_N];
int ebm, ebm2, ebm3, eb, en;
int uzak[MAX_N][2], kul[MAX_N];
int DFS(int dugum, int ata) {
kul[dugum] = 1;
for (int i = 0; i < E[dugum].size(); i++) {
int v = E[dugum][i].first, m = E[dugum][i].second;
if (v != ata) {
int s = DFS(v, dugum) + m;
if(s > uzak[dugum][0]) {
uzak[dugum][1] = uzak[dugum][0];
uzak[dugum][0] = s;
}
else if(s > uzak[dugum][1])
uzak[dugum][1] = s;
}
}
// printf("dugum: %d, ata: %d, uzak0: %d, uzak1: %d\n", dugum, ata,uzak[dugum][0], uzak[dugum][1]);
return uzak[dugum][0];
}
void DFS2(int dugum, int ata, int m) {
//printf("Dugum: %d, ata: %d, m: %d, eb: %d, uzak[dugum][0]: %d\n", dugum, ata, m, eb, uzak[dugum][0]);
if (ata != -1)
if (uzak[ata][0] == uzak[dugum][0] + m) {
if (uzak[dugum][0] < uzak[ata][1] + m) {
uzak[dugum][1] = uzak[dugum][0];
uzak[dugum][0] = uzak[ata][1] + m;
}
else if (uzak[dugum][1] < uzak[ata][1] + m)
uzak[dugum][1] = uzak[ata][1] + m;
}
else {
if (uzak[dugum][0] < uzak[ata][0] + m) {
uzak[dugum][1] = uzak[dugum][0];
uzak[dugum][0] = uzak[ata][0] + m;
}
else if (uzak[dugum][1] < uzak[ata][0] + m)
uzak[dugum][1] = uzak[ata][0] + m;/*
uzak[dugum][1] = uzak[dugum][0];
uzak[dugum][0] = uzak[ata][0] + m;
uzak[dugum][1] = max(uzak[dugum][1], uzak[ata][1] + m);*/
}
//printf("Dugum: %d, ata: %d, m: %d, eb: %d, uzak[dugum][0]: %d\n", dugum, ata, m, eb, uzak[dugum][0]);
for (int i = 0; i < E[dugum].size(); i++) {
int v = E[dugum][i].first, mm = E[dugum][i].second;
if (v != ata)
DFS2(v, dugum, mm);
}
//printf("Dugum: %d, ata: %d, m: %d, eb: %d, uzak[dugum][0]: %d\n", dugum, ata, m, eb, uzak[dugum][0]);
eb = min(eb, uzak[dugum][0]);
en = max(en, uzak[dugum][0]);
}
void merkezleriBul(int N) {
for (int i = 0; i < N; i++) {
if (!kul[i]) {
eb = oo;
DFS(i, -1);
DFS2(i, -1, 0);
printf("%d\n", eb);
if (eb > ebm) {ebm3 = ebm2; ebm2 = ebm; ebm = eb;}
else if (eb > ebm2) {ebm3 = ebm2; ebm2 = eb;}
else if (eb > ebm3) ebm3 = eb;
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
E[ A[i] ].push_back( make_pair(B[i], T[i]) );
E[ B[i] ].push_back( make_pair(A[i], T[i]) );
}
merkezleriBul(N);
int sonuc;
sonuc = max(ebm + ebm2 + L, ebm2 + ebm3 + 2*L);
sonuc = max(sonuc, en);
return sonuc;
}
Compilation message
dreaming.cpp: In function 'int DFS(int, int)':
dreaming.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E[dugum].size(); i++) {
~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void DFS2(int, int, int)':
dreaming.cpp:37:5: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
if (ata != -1)
^
dreaming.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E[dugum].size(); i++) {
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
10748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
10748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
10748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
6264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
10748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
10748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
