Submission #1021250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021250		Thanhs	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	265 ms	103856 KiB

worst_reporter2

#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;
 
int A[N], H[N], C[N], deg[N];
map<int, int> cnt[N];

void merge(map<int, int>& a, map<int, int>& b)
{
    if (a.size() < b.size()) swap(a, b);
    for (auto t : b) a[t.fi] += t.se;
}

void fix(map<int, int>& a, int b, int c)
{
    a[b] += c; auto it = a.find(b);
    while (it != a.begin())
    {
        it--;
        if ((*it).se > c) {(*it).se -= c; break;}
        c -= (*it).se; it = a.erase(it);
    }
}

signed main()
{
    if (fopen("in.txt", "r")) {
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    }
    fastIO
    int n, sum = 0; 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> A[i] >> H[i] >> C[i], sum += C[i], deg[A[i]]++;
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!deg[i]) q.push(i);
    while (!q.empty())
    {
        int u = q.front(), crr = C[u]; q.pop();
        deg[A[u]]--;
        fix(cnt[u], H[u], C[u]);
        merge(cnt[A[u]], cnt[u]);
        if (!deg[A[u]]) q.push(A[u]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!deg[i]) continue;
        deg[i] = 0;
        map<int, int> all = cnt[i], cn;
        cn[H[i]] += C[i];
        for (int crr = A[i]; crr != i; crr = A[crr])
            merge(all, cnt[crr]), deg[crr] = 0, cn[H[crr]] += C[crr];
        for (auto t : cn) fix(all, t.fi, t.se);
        for (auto t : all) sum -= t.se;
    }
    cout << sum;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:62:28: warning: unused variable 'crr' [-Wunused-variable]
   62 |         int u = q.front(), crr = C[u]; q.pop();
      |                            ^~~
worst_reporter2.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("in.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("out.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 21 / 21