| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 218873 |
2020-04-02T23:50:15 Z |
bigg |
Dreaming (IOI13_dreaming) |
C++11 |
|
60 ms |
15604 KB |
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
int n, m, l;
vector<pair<int, int> > grafo[112345];
vector<int> comp[112345];
int compid[112345];
int altura[112345];
int centro[112345], maxraio[112345];
int marc1[112345], marc2[112345], marc3[112345];
int maxd, maxdi, qtdcomp, cf, cfi;
void dfs1(int x){
marc1[x] = 1;
comp[qtdcomp].push_back(x);
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(!marc1[viz]){
altura[viz] = altura[x] + grafo[x][i].second;
if(altura[viz] >= maxd){
maxd = altura[viz];
maxdi = viz;
}
dfs1(viz);
}
}
}
void dfs2(int x){
marc2[x] = 1;
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(!marc2[viz]){
altura[viz] = altura[x] + grafo[x][i].second;
maxd = max(maxd, altura[viz]);
dfs2(viz);
}
}
}
void dfs3(int x){
marc3[x] = 1;
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(!marc3[viz]){
altura[viz] = altura[x] + grafo[x][i].second;
maxd = max(maxd, altura[viz]);
dfs3(viz);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, l = L;
for(int i = 0; i < m; i++){
//int a, b, t;
//scanf("%d %d", &a, &b, &t);
grafo[A[i]].push_back(make_pair(B[i], T[i]));
grafo[B[i]].push_back(make_pair(A[i], T[i]));
}
//printf("%d\n", n);
for(int i = 0; i < n; i++){
if(!marc1[i]){
maxd = 0;
dfs1(i);
altura[maxdi] = 0;
maxd = 0;
dfs2(maxdi);
int centrodesse = 1e9 + 7, cdi;
for(int j = 0; j < comp[qtdcomp].size(); j++){
if(abs(altura[comp[qtdcomp][j]] - maxd/2) <= centrodesse){
cdi = comp[qtdcomp][j];
centrodesse = abs(altura[comp[qtdcomp][j]] - maxd/2);
}
}
centro[qtdcomp] = cdi;
maxd = 0;
altura[cdi] = 0;
dfs3(cdi);
maxraio[qtdcomp] = maxd;
qtdcomp++;
}
}
for(int i = 0; i < qtdcomp; i++){
if(maxraio[i] > cf){
cf = maxraio[i];
cfi = i;
}
}
int ans = 0;
//printf("%d\n", maxraio[cfi]);
for(int i = 0; i < qtdcomp; i++){
if(i == cfi) continue;
ans = max(l + maxraio[cfi] + maxraio[i],ans);
//printf("%d\n", l + maxraio[cfi] + maxraio[i]);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++){
~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++){
~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs3(int)':
dreaming.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++){
~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < comp[qtdcomp].size(); j++){
~~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:89:20: warning: 'cdi' may be used uninitialized in this function [-Wmaybe-uninitialized]
centro[qtdcomp] = cdi;
~~~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
15604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
15604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
15604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
12280 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
12280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
15604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
15604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
