이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |