首页 > 代码库 > BestCoder Round #1 第二题 项目管理
BestCoder Round #1 第二题 项目管理
// 第二题 我记得很久很久很久以前看过这样的题目,忘记是哪的区域赛了
// 记得有人说和节点度数有关,我记不清了,反正当时完全不懂
// 然后我想了想,估计就是更新节点度数有关,YY出来可能只要更新相邻节点度数更大或更小的就可以了
// 复杂度不知道多少,就是提交了试试,15MS就过了
// 看来就是这样了
// 具体就是求出每个节点度数,然后每次更新时,只要更新与自己相连,但度数比自己大的
// 查询时把度数自己大的节点累加的值加上就可输出,具体看代码比较清楚
// 也就做得来这2题了(见识少,以前题目做得少)。
// 不过在厦门实训感觉蛮悠闲,企业上课就是比学校效率
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#include <vector>#include <map>#include <queue>using namespace std;#define LL long long#define N 100010#define mod 1000000007vector<int> V[N],up[N];//V记录边,up记录邻接节点,但度数自己大int in[N];//记录节点度数int sum[N],add[N];//add 保存更新int main(){ // priority_queue<int,vector<int>,greater<int> > int T; int n,m,Q; int a,b; int i,j; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); for(i=1;i<=n;i++){ V[i].clear(); in[i]=0; up[i].clear(); sum[i]=add[i]=0; } while(m--) { scanf("%d %d",&a,&b); V[a].push_back(b); V[b].push_back(a); in[b]++; in[a]++; } for(a=1;a<=n;a++) for(j=0;j<V[a].size();j++) { b=V[a][j]; if(in[b]>=in[a]) up[a].push_back(b); } scanf("%d",&Q); int cmd,u,v; while(Q--) { scanf("%d %d",&cmd,&u); if(cmd==0) { scanf("%d",&v); add[u]+=v; for(i=0; i<up[u].size(); i++) { j=up[u][i]; sum[j]+=v; } } else { int ans=sum[u]; for(i=0; i<up[u].size(); i++) { j=up[u][i]; if(in[j]!=in[u]) ans+=add[j]; } printf("%d\n",ans); } } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。