Konrad and Company Evaluation
发布时间:2020-12-14 21:42:52 所属栏目:大数据 来源:网络整理
导读:F. Konrad and Company Evaluation 参考:[codeforces 1230F]Konrad and Company Evaluation-暴力 思路:题意分析见参考博客。因为求的是三元组的个数,所以在保存的时候的时候就保存为有向图,让工资少的员工指向工资多的员工,那么求三元组的时候,只需要
F. Konrad and Company Evaluation
代码: // Created by CAD on 2019/10/1. #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e6+5; int cnt[maxn]; vector<int> g[maxn]; ll cal(int i) { return (cnt[i]-g[i].size())*g[i].size(); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=1,u,v;i<=m;++i) { cin>>u>>v; if(u>v) swap(u,v); g[u].push_back(v); cnt[u]++,cnt[v]++; } ll ans=0; for(int i=1;i<=n;++i) ans+=cal(i); int q; cin>>q; cout<<ans<<endl; while(q--) { int x; cin>>x; ans-=cal(x); for(auto i:g[x]) { ans-=cal(i); g[i].push_back(x); ans+=cal(i); g[x].clear(); } cout<<ans<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |