# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41970 | OneSubmissionMan | 구슬과 끈 (APIO14_beads) | C++11 | 51 ms | 52472 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# include <bits/stdc++.h>
# define F first
# define S second
# define mp make_pair
// everything go according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1 Y_U_NO_y1
# define left Y_U_NO_left
# define right Y_U_NO_right
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef long double ld;
const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
ios_base :: sync_with_stdio(0);
cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
unsigned int seed;
asm ("rdtsc" : "=A"(seed));
srand (seed);
}
void files (string problem) {
if (fopen ((problem + ".in").c_str(),"r")) {
freopen ((problem + ".in").c_str(),"r",stdin);
freopen ((problem + ".out").c_str(),"w",stdout);
}
}
void localInput (string in = "s") {
if (fopen (in.c_str(), "r"))
freopen (in.c_str(), "r", stdin);
else {
cerr << "Input file not found" << endl;
}
}
ll dp[2][Sz];
int n;
vec<int> g[Sz], w[Sz];
void dfs (int v, int pr) {
for (int to : g[v]) {
if (to != pr)
dfs (to, v);
}
int mx1 = -2e9;
int mx2 = -2e9;
ll sum = 0;
ll up = 0;
int cnt = 0;
for (int i = 0; i < sz(g[v]); i++) {
int to = g[v][i];
int len = w[v][i];
if (to == pr) {
up = len;
continue;
}
cnt++;
sum += dp[1][to];
int val = dp[0][to] + len - dp[1][to];
if (mx1 < val)
mx2 = mx1, mx1 = val;
else
mx2 = max (mx2, val);
}
if (cnt >= 2)
dp[0][v] = max (0ll, sum + 0ll + mx1 + mx2);
dp[0][v] = max (dp[0][v], sum);
dp[1][v] = dp[0][v];
if (cnt >= 1)
dp[1][v] = max (dp[1][v], sum + mx1 + up);
}
int main()
{
Read_rap();
//localInput();
cin >> n;
for (int i = 1; i < n; i++) {
int x, y, z; cin >> x >> y >> z;
g[x].pb (y);
w[x].pb (z);
g[y].pb (x);
w[y].pb (z);
}
dfs (1, 1);
cout << dp[0][1];
return 0;
}
// Coded by Z..
Compilation message (stderr)
# | 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... |