# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41947 | 2018-02-22T06:20:51 Z | OneSubmissionMan | Beads and wires (APIO14_beads) | C++11 | 48 ms | 52728 KB |
# 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; } } int 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; int sum = 0; int up = 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; } 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 (sz(g[v]) >= 3) dp[0][v] = sum + mx1 + mx2; dp[0][v] = max (dp[0][v], sum); if (sz(g[v]) >= 2) dp[1][v] = max (0, sum + up + mx1); } 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 52728 KB | Output is correct |
2 | Correct | 46 ms | 52472 KB | Output is correct |
3 | Correct | 48 ms | 52536 KB | Output is correct |
4 | Correct | 47 ms | 52520 KB | Output is correct |
5 | Correct | 46 ms | 52472 KB | Output is correct |
6 | Incorrect | 46 ms | 52480 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 52728 KB | Output is correct |
2 | Correct | 46 ms | 52472 KB | Output is correct |
3 | Correct | 48 ms | 52536 KB | Output is correct |
4 | Correct | 47 ms | 52520 KB | Output is correct |
5 | Correct | 46 ms | 52472 KB | Output is correct |
6 | Incorrect | 46 ms | 52480 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 52728 KB | Output is correct |
2 | Correct | 46 ms | 52472 KB | Output is correct |
3 | Correct | 48 ms | 52536 KB | Output is correct |
4 | Correct | 47 ms | 52520 KB | Output is correct |
5 | Correct | 46 ms | 52472 KB | Output is correct |
6 | Incorrect | 46 ms | 52480 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 52728 KB | Output is correct |
2 | Correct | 46 ms | 52472 KB | Output is correct |
3 | Correct | 48 ms | 52536 KB | Output is correct |
4 | Correct | 47 ms | 52520 KB | Output is correct |
5 | Correct | 46 ms | 52472 KB | Output is correct |
6 | Incorrect | 46 ms | 52480 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |