# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1021199 | Thanhs | Worst Reporter 4 (JOI21_worst_reporter4) | C++14 | 10 ms | 14504 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |