Codeforces Round #588 (Div. 1) C. Konrad and Company Evaluation
2024-09-04 08:31:22
直接建反边暴力 复杂度分析见https://blog.csdn.net/Izumi_Hanako/article/details/101267502
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = ;
ll out[MAXN], in[MAXN];
vector<int> G[MAXN];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
if (u < v) {
swap(u, v);
}
out[u]++, in[v]++;
G[v].push_back(u);
}
ll ans = ;
for (int i = ; i <= n; i++) {
ans += out[i] * in[i];
}
cout << ans << endl;
int Q;
scanf("%d", &Q);
while (Q--) {
int x;
scanf("%d", &x);
ans -= out[x] * in[x];
out[x] += G[x].size(), in[x] = ;
for (int v : G[x]) {
ans -= out[v] * in[v];
out[v]--, in[v]++;
ans += out[v] * in[v];
G[v].push_back(x);
}
G[x].clear();
cout << ans << endl;
}
return ;
}
最新文章
- java的动态代理机制详解
- git push命令
- JSLint JavaScript代码质量审查工具汉化中文版隆重发布
- Ubuntu 启动黑屏解决
- Linux01--文件管理,常用命令 权限管理
- JQuery操作元素的属性与样式及位置 复制代码
- 【★】深入BGP原理和思想【第一部】
- oracle安装时,条件检查不通过解决办法
- 51 nod 1297 管理二叉树
- ejabberd开发和部署
- C#实现联通短信Sgip协议程序源码
- Firefox下载附件乱码的解决办法
- python面试题--数据类型
- 1.4 Chrome浏览器
- UX设计秘诀之注册表单设计,细节决定成败
- HTTP 协议入门-笔记
- html5 的localstorage
- 在VMware中设置CentOS7的网络
- PIP安装时报The repository located at pypi.douban.com is not a trusted or secure host and is being ignore
- UnicodeEncodeError: &#39;ascii&#39; codec can&#39;t encode character u&#39;\xe9&#39; in position 7: ordinal not in range(128) [duplicate]