제출 #248930

#제출 시각아이디문제언어결과실행 시간메모리
248930patrikpavic2구슬과 끈 (APIO14_beads)C++17
57 / 100
677 ms114452 KiB
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <unordered_map> #include <ext/pb_ds/assoc_container.hpp> #define X first #define Y second #define PB push_back using namespace std; using namespace __gnu_pbds; typedef pair < int, int > pii; const int N = 2e5 + 500; const int INF = 2e9; vector < pii > v[N]; gp_hash_table < int, int > dp[3]; gp_hash_table < int, int > vr; int zbr[N]; vector < pair < int, int > > kand[N]; int n, jesam[N]; int f(int x, int fl, int lst){ if(dp[fl][x * (N - 37) + lst] != 0) return dp[fl][x * (N - 37) + lst] - 1; //printf("x = %d fl = %d lst = %d\n", x, fl, lst); //char c; scanf("%c", &c); if(!jesam[x]){ int sm = 0; for(pii nxt : v[x]){ if(nxt.X == lst) continue; int opt = max(f(nxt.X, 0, x), f(nxt.X, 1, x) + (int)nxt.Y); sm += opt; kand[x].PB({f(nxt.X, 2, x) + nxt.Y - opt, nxt.X}); } kand[x].PB({-INF, -1}); kand[x].PB({-INF, -1}); sort(kand[x].rbegin(), kand[x].rend()); jesam[x] = (x == lst ? n + 1 : lst); zbr[x] = sm; return (dp[fl][x * (N - 37) + lst] = sm + kand[x][0].X * (fl == 1) + 1) - 1; } if(jesam[x] == lst){ return (dp[fl][x * (N - 37) + lst] = zbr[x] + kand[x][0].X * (fl == 1) + 1) - 1; } if(jesam[x] < n + 1){ int opt = max(f(jesam[x], 0, x), f(jesam[x], 1, x) + vr[x * (N - 37) + jesam[x]]); zbr[x] += opt; kand[x].PB({f(jesam[x], 2, x) + vr[x * (N - 37) + jesam[x]] - opt, jesam[x]}); sort(kand[x].rbegin(), kand[x].rend()); jesam[x] = n + 1; } int sm = zbr[x] - (x == lst ? 0 : max(f(lst, 0, x), f(lst, 1, x) + vr[x * (N - 37) + lst])); int dod = kand[x][0].X; if(kand[x][0].Y == lst) dod = kand[x][1].X; //printf("x = %d fl = %d lst = %d --> %intd + %intd\n", x, fl, lst, sm , dod * (fl == 1)); return (dp[fl][x * (N - 37) + lst] = sm + dod * (fl == 1) + 1) - 1; } int main(){ scanf("%d", &n); for(int i = 1;i < n;i++){ int x, y, z; scanf("%d%d%d", &x, &y, &z); v[x].PB({y, z}), v[y].PB({x, z}); vr[x * (N - 37) + y] = z, vr[y * (N - 37) + x] = z; } int sol = 0; for(int i = 1;i <= n;i++) sol = max(sol, f(i, 0, i)); printf("%d\n", sol); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp: In function 'int main()':
beads.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:70:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...