Codeforces Gym 100650B Countdown （离线）

题目链接：http://codeforces.com/gym/100650

根据给出的树和d，求出一些结点，这些结点形成子树的第d层结点数应该尽量多，具体要求可以参考题目。

dfs一个结点前保存询问深度的答案，访问完以后减去之前的值就得到答案了。

#include<bits/stdc++.h> using namespace std; const int maxn = 1100;vector<string> names; map<string,int> mp; int id_cnt; #define se second #define MP make_pairint ID(const string & s){map<string,int>::iterator i = mp.find(s);if(i != mp.end()) return i->se;names.push_back(s);mp.insert(MP(s,id_cnt));return id_cnt++; } int deg[maxn]; int head[maxn],nxt[maxn],to[maxn],ecnt;void addEdge(int u,int v) {to[ecnt] = v;nxt[ecnt] = head[u];head[u] = ecnt++; }int pre[maxn*2]; int cnt[maxn*2]; int deep[maxn];struct Node {int d,id;bool operator < (const Node & x) const {return d < x.d || ( d == x.d && names[id] > names[x.id] );} };priority_queue<Node> q;int n,d; void dfs(int u) {cnt[deep[u]]++;int qd = deep[u]+d;if(qd < maxn) pre[u] = cnt[qd];for(int i = head[u]; ~i; i = nxt[i]){int v = to[i];deep[v] = deep[u]+1;dfs(v);}if(qd<maxn){int ans = cnt[qd]-pre[u];if(ans) q.push(Node{ans,u});} }void init() {names.clear();mp.clear();id_cnt = 0;ecnt = 0;memset(deg,0,sizeof(deg));memset(head,-1,sizeof(head));memset(cnt,0,sizeof(cnt));while(q.size()) q.pop(); }char str[500];void read() {scanf("%d%d",&n,&d);while(n--){int ch; scanf("%s%d",str,&ch);int fa = ID(str);while(ch--){scanf("%s",str);int v = ID(str);deg[v]++;addEdge(fa,v);}} }void topo() {int root;n = mp.size();for(int i = 0; i < n; i++){if(deg[i] == 0) { root = i; break; }}deep[root] = 0;dfs(root); }int main() {//freopen("in.txt","r",stdin);int T; scanf("%d",&T);for(int kas = 1; kas <= T; kas++){init();read();topo();printf("Tree %d:\n",kas);for(int i = 1; i <= 3; i++){if(q.empty()) break;Node x = q.top(); q.pop();printf("%s %d\n",names[x.id].c_str(),x.d);if(i == 3){int pre = x.d;while(q.size()){x = q.top(); q.pop();if(x.d == pre){printf("%s %d\n",names[x.id].c_str(),x.d);}else {break;}}}}if(kas != T) putchar('\n');}return 0; }

 

转载于:https://www.cnblogs.com/jerryRey/p/4740203.html

总结

以上是生活随笔为你收集整理的Codeforces Gym 100650B Countdown （离线）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。