oj.uz

Submission #1021223

# Submission time Handle Problem Language Result Execution time Memory
1021223 2024-07-12T15:58:05 Z Thanhs Worst Reporter 4 (JOI21_worst_reporter4) C++14
0 / 100
 11 ms 19288 KB 
#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], r[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];
    int t = a[u];
    while (s[u].find(a[u]) != s[u].begin())
    {
        auto it = s[u].find(a[u]);
        if ((*prev(it)).se <= t) 
        {
            t -= (*prev(it)).se;
            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);
            r[u].push_back(v);
        }
    }
    int ans = accumulate(c + 1, c + 1 + n, 0ll);
    dfs_size();
    dfs();
    for (auto t : s[1]) ans -= t.se;
    cout << ans;
}

Compilation message

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19196 KB Output is correct
3 Incorrect 9 ms 19288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19196 KB Output is correct
3 Incorrect 9 ms 19288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19196 KB Output is correct
3 Incorrect 9 ms 19288 KB Output isn't correct
4 Halted 0 ms 0 KB -