이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=2e5+5;
int N;
int A[MX],H[MX],C[MX];
vector<int> adj[MX];
multiset<pair<ll,ll>> dp[MX];
int par[MX];
int find(int v) {
return par[v]==v?v:par[v]=find(par[v]);
}
void merge(int u, int v) {
u=find(u),v=find(v);
if(u==v) return;
if(dp[u].size()>dp[v].size()) swap(u,v);
for(auto [pos,val]:dp[u]) {
dp[v].insert({pos,val});
}
par[u]=v;
dp[u].clear();
}
void dfs(int v) {
int prv=-1;
for(auto u:adj[v]) {
dfs(u);
if(prv!=-1)
merge(u,prv);
prv=u;
}
if(prv!=-1) merge(v,prv);
int pv=find(v);
auto it=dp[pv].lower_bound(make_pair(H[v],0));
if(it==dp[pv].begin()) {
dp[pv].insert(make_pair(H[v],C[v]));
} else {
it--;
ll cur=C[v];
while(true) {
if(cur>=it->second) {
cur-=it->second;
it=dp[pv].erase(it);
if(it==dp[pv].begin()) break;
it--;
} else {
auto [p,q]=*it;
dp[pv].erase(it);
dp[pv].insert({p,q-cur});
cur=0;
break;
}
}
dp[pv].insert(make_pair(H[v],C[v]));
}
}
int onstk[MX],degs[MX],head[MX];
vector<int> stk;
void dfs0(int v) {
onstk[v]=1;
stk.push_back(v);
if(onstk[A[v]]==0) {
dfs0(A[v]);
} else if(onstk[A[v]]==1) {
vector<int> cyc;
for(int i=stk.size()-1;i>=0;i--) {
cyc.push_back(stk[i]);
if(stk[i]==A[v]) break;
}
sort(cyc.begin(),cyc.end(),[&](int i, int j){
if(H[i]==H[j]) return C[i]>C[j];
return H[i]>H[j];
});
for(int i=0;i+1<cyc.size();i++) {
head[cyc[i+1]]=cyc.back();
A[cyc[i+1]]=cyc[i];
}
head[cyc[0]]=cyc.back();
A[cyc[0]]=cyc[0];
}
stk.pop_back();
onstk[v]=2;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N;
ll sum=0;
for(int i=1;i<=N;i++) {
cin>>A[i]>>H[i]>>C[i];
sum+=C[i];
head[i]=i;
}
for(int i=1;i<=N;i++) {
if(onstk[i]==2) continue;
dfs0(i);
}
for(int i=1;i<=N;i++) {
if(A[i]!=i) {
if(head[A[i]]!=head[i]) {
adj[head[A[i]]].push_back(head[i]);
degs[head[i]]+=1;
} else {
adj[A[i]].push_back(i);
degs[i]+=1;
}
}
}
for(int i=1;i<=N;i++) par[i]=i;
ll ans=0;
for(int i=1;i<=N;i++) {
if(degs[i]==0) {
dfs(i);
ll s=0;
for(auto [pos,val]:dp[find(i)])
s+=val;
ans+=s;
}
}
cout<<sum-ans<<'\n';
}
컴파일 시 표준 에러 (stderr) 메시지
worst_reporter2.cpp: In function 'void dfs0(int)':
worst_reporter2.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=0;i+1<cyc.size();i++) {
| ~~~^~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |