Submission #1021199

#TimeUsernameProblemLanguageResultExecution timeMemory
1021199ThanhsWorst Reporter 4 (JOI21_worst_reporter4)C++14
0 / 100
10 ms14504 KiB
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double #define pb push_back #define endl '\n' #define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define setmin(x, y) x = min((x), (y)) #define setmax(x, y) x = max((x), (y)) #define sqr(x) (x) * (x) #define fi first #define se second mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count()); int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);} const int N = 2e5 + 5; const int mod = 998244353; const int SQ = 450; const int inf = 1e9; const int bound = 1e7; vector<int> g[N]; map<int, int> s[N]; int n, sz[N], a[N], c[N]; void dfs(int u = 1) { int bc = 0; for(int v:g[u]) if(sz[v] > sz[bc]) bc=v; for (int v : g[u]) dfs(v); if (bc) swap(s[u], s[bc]); for (int v : g[u]) if (v != bc) for (auto t : s[v]) s[u][t.fi] += t.se; s[u][a[u]] += c[u]; while (s[u].find(a[u]) != s[u].begin()) { auto it = s[u].find(a[u]); if ((*prev(it)).se <= c[u]) s[u].erase(prev(it)); else { s[u][(*prev(it)).fi] -= c[u]; break; } } // cout << u << ": {"; // for (auto t : s[u]) cout << '(' << t.fi << ", " << t.se << ") "; cout << "}\n"; } int dfs_size(int u = 1, int p = 0) { sz[u] = 1; for (auto v : g[u]) if (v != p) sz[u] += dfs_size(v); return sz[u]; } signed main() { if (fopen("in.txt", "r")) { freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); } fastIO cin >> n; for (int u = 1; u <= n; u++) { int v; cin >> v >> a[u] >> c[u]; if (u != v) g[v].push_back(u); } int ans = accumulate(c + 1, c + 1 + n, 0ll); dfs_size(); dfs(); for (auto t : s[1]) ans -= t.se; cout << ans; }

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("in.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen("out.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...