Submission #607228

#TimeUsernameProblemLanguageResultExecution timeMemory
6072281binMagic Tree (CEOI19_magictree)C++14
100 / 100
152 ms38528 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 1e5 + 5; ll n, m, k, a, b, c, p, d[NMAX], w[NMAX], ii[NMAX]; vector<int> adj[NMAX]; map<int, ll> mp[NMAX]; void merge(int a, int b){ if(mp[ii[a]].size() < mp[ii[b]].size()) swap(ii[a], ii[b]); for(auto&[x, y] : mp[ii[b]]) mp[ii[a]][x] += y; return; } void dfs(int x){ for(int & nx : adj[x]) { dfs(nx); merge(x, nx); } if(w[x]){ mp[ii[x]][d[x]] += w[x]; auto it = mp[ii[x]].upper_bound(d[x]); while(it != mp[ii[x]].end()){ if(w[x] < it->second){ it->second -= w[x]; break; } auto nx = next(it); nx->second += it->second; it = mp[ii[x]].erase(it); } } return; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> k; for(int i = 1; i <= n; i++) ii[i] = i; for(int i = 2; i <= n; i++){ cin >> p; adj[p].emplace_back(i); } while(m--){ cin >> a; cin >> d[a] >> w[a]; } dfs(1); ll ans = 0; for(auto& [x, y] : mp[ii[1]]) ans += y; cout << ans; return 0; }

Compilation message (stderr)

magictree.cpp: In function 'void merge(int, int)':
magictree.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto&[x, y] : mp[ii[b]]) mp[ii[a]][x] += y;
      |              ^
magictree.cpp: In function 'int main()':
magictree.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for(auto& [x, y] : mp[ii[1]]) ans += y;
      |               ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...