제출 #1215397

#제출 시각아이디문제언어결과실행 시간메모리
1215397jerzykSecurity Guard (JOI23_guard)C++20
37 / 100
86 ms33096 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1'000'000'000'000'000'000LL; const int II = 2'000'000'000; const ll M = 1'000'000'007LL; const int N = 1<<18; int vis[N]; vector<int> ed[N]; int tab[N]; ll dps[N], dpm[N]; ll ans = I; void DFS(int v) { vis[v] = 1; dps[v] = ((ll)ed[v].size() - 1LL) * (ll)tab[v]; for(int i = 0; i < (int)ed[v].size(); ++i) { int ne = ed[v][i]; if(vis[ne]) continue; DFS(ne); dps[v] += dps[ne]; dpm[v] = max(dpm[v], dpm[ne] + (ll)(tab[ne] - tab[v])); } vis[v] = 0; } void DFSP(int v) { vis[v] = 1; ll m1 = 0LL, m2 = 0LL; for(int i = 0; i < (int)ed[v].size(); ++i) { int ne = ed[v][i]; ll a = max(0LL, dpm[ne] + (ll)(tab[ne] - tab[v])); if(a > m1) swap(a, m1); if(a > m2) swap(a, m2); } //cout << "C: " << v << " " << m1 << " " << dps[1] << "\n"; ans = min(ans, dps[1] + (ll)tab[v] + m1); for(int i = 0; i < (int)ed[v].size(); ++i) { int ne = ed[v][i]; if(vis[ed[v][i]]) continue; ll a = max(0LL, dpm[ne] + (ll)(tab[ne] - tab[v])); dpm[v] = m1; if(a == m1) dpm[v] = m2; DFSP(ed[v][i]); } vis[v] = 0; } void Solve() { int n, m, a, b, q, ma = 0; cin >> n >> m >> q; for(int i = 1; i <= n; ++i) { cin >> tab[i]; ma = max(ma, tab[i]); } for(int i = 1; i <= m; ++i) { cin >> a >> b; ed[a].pb(b); ed[b].pb(a); } DFS(1); //DFSP(1); cout << dps[1] + ma << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //int t; cin >> t; //while(t--) Solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...