Submission #356368

#TimeUsernameProblemLanguageResultExecution timeMemory
356368sean617Dreaming (IOI13_dreaming)C++98
47 / 100
170 ms25324 KiB
#include "dreaming.h" #include <iostream> #include <cstdio> #include <vector> #define SZ 100005 using namespace std; int MM = 2e9; int n, m, mx, po, cnt, mn, md, ans, m1, m2, m3, v[SZ], h1[SZ], h2[SZ], num1[SZ], num2[SZ]; vector<int> a[SZ], b[SZ], c; //void f(int p, int q, int w) { // int i, t; // if (w > mx) { // mx = w; // po = p; // } // v[p] = cnt; // for (i = 0; i < a[p].size(); i++) { // t = a[p][i]; // if (t == q) continue; // f(t, p, w + b[p][i]); // } //} // //int g(int p, int q, int w) { // int i, t, t2; // if (w == mx) return 1; // for (i = 0; i < a[p].size(); i++) { // t = a[p][i]; // if (t == q) continue; // if (g(t, p, w + b[p][i])) { // t2 = max(w, mx - w); // mn = min(mn, t2); // return 1; // } // } // return 0; //} int f(int p, int q) { int i, t, mx1 = 0, mx2 = 0, t2, n1, n2; v[p] = cnt; for (i =0 ; i < a[p].size(); i++) { t = a[p][i]; if (t == q) continue; t2 = f(t, p) + b[p][i]; if (t2 > mx1) { n2 = n1; n1 = t; mx2 = mx1; mx1 = t2; } else if (t2 > mx2) { mx2 = t2; n2 = t; } } h1[p] = mx1; h2[p] = mx2; num1[p] = n1; num2[p] = n2; return mx1; } int g(int p, int q, int w) { int i, t, tt, t1, mx1 = 0; for (i = 0; i < a[p].size(); i++) { t = a[p][i]; if (t == q) continue; if (num1[p] == t) t1 = h2[p]; else t1 = h1[p]; t1 = max(t1, w); mx1 = max(mx1, g(t, p, t1 + b[p][i]) + b[p][i]); } tt = max(w, mx1); mx = max(mx, tt); mn = min(mn, tt); return mx1; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { int i, j, t1, t2, t3; n = N; m = M; for (i = 0; i < m; i++) { // scanf ("%d %d %d", &t1, &t2, &t3); t1 = A[i]; t2 = B[i]; t3 = T[i]; a[t1].push_back(t2); a[t2].push_back(t1); b[t1].push_back(t3); b[t2].push_back(t3); } for (i = 0; i < n; i++) { if (v[i]) continue; cnt++; mx = 0; mn = MM; f(i, 0); g(i, 0, 0); // mx = -1; // c.clear(); // f(i, 0, 0); // c.push_back(po); // mx = -1; // f(po, 0, 0); // ans = max(ans, mx); // c.push_back(po); // if (mx == 0) { // continue; // } // mn = MM; // g(c[0], 0, 0); if (mn > m1) { m3 = m2; m2 = m1; m1 = mn; } else if (mn > m2) { m3 = m2; m2 = mn; } else if (mn > m3) { m3 = mn; } ans = max(ans, mx); // printf("%d %d\n", c[0], c[1]); } if (m == n - 1) { cout << ans; return 0; } ans = max(ans, m1 + m2 + L); if (cnt >= 3) ans = max(ans, m2 + m3 + L * 2); return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'int f(int, int)':
dreaming.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (i =0 ; i < a[p].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'int g(int, int, int)':
dreaming.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (i = 0; i < a[p].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:81:12: warning: unused variable 'j' [-Wunused-variable]
   81 |     int i, j, t1, t2, t3;
      |            ^
dreaming.cpp: In function 'int f(int, int)':
dreaming.cpp:60:13: warning: 'n2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     num2[p] = n2;
      |     ~~~~~~~~^~~~
dreaming.cpp:59:13: warning: 'n1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     num1[p] = n1;
      |     ~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...