제출 #83194

#제출 시각아이디문제언어결과실행 시간메모리
83194RezwanArefin01구슬과 끈 (APIO14_beads)C++17
0 / 100
10 ms9728 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, int> ii; const int N = 2e5 + 10; vector<int> adj[N], cost[N]; ll S[N], M[N], ans; int n, pcost[N]; void calc(int u, int par) { for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i], c = cost[u][i]; if(v == par) continue; pcost[v] = c; calc(v, u); S[u] += max(S[v], M[v]); } for(int v : adj[u]) if(v - par) { M[u] = max(M[u], S[u] - max(S[v], M[v]) + S[v] + pcost[u] + pcost[v]); } } void solve(int u, int par) { ans = max(ans, S[u]); vector<ii> l = {{-1e18, 0}}; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i], c = cost[u][i]; if(v == par) continue; l.push_back({-max(S[v], M[v]) + S[v] + c, v}); } sort(l.begin(), l.end(), greater<ii>()); for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i], c = cost[u][i]; if(v == par) continue; ll a = S[u], b = S[v], C = M[u], d = M[v]; S[u] -= max(S[v], M[v]); M[u] = S[u] + c + (l[0].second == v ? l[1].first : l[0].first); S[v] += max(S[u], M[u]); solve(v, u); S[u] = a, S[v] = b, M[u] = C, M[v] = d; } } int main() { int n; scanf("%d", &n); for(int i = 1; i < n; i++) { int u, v, c; scanf("%d %d %d", &u, &v, &c); adj[u].push_back(v); adj[v].push_back(u); cost[u].push_back(c); cost[v].push_back(c); } calc(1, 0); solve(1, 0); printf("%lld\n", ans); }

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

beads.cpp: In function 'void calc(int, int)':
beads.cpp:13:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void solve(int, int)':
beads.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
beads.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf("%d", &n);
            ~~~~~^~~~~~~~~~
beads.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &u, &v, &c); 
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...