热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

[构造]CodeforcesGym101190NEERC16C.CactusConstruction

我们递归地搞使得包含点P的某个仙人掌被构造出来且除了P是1其他都是2然后就是拆桥边或拆环递归下去然后在合起来就行了把桥边接起来很显然环的话自己画画也不难搞出来了吧#inc

我们递归地搞 使得包含点P的某个仙人掌被构造出来且除了P是1其他都是2
然后就是拆桥边或拆环 递归下去 然后在合起来就行了
把桥边接起来很显然 环的话 自己画画也不难搞出来了吧

#include
#include
#include
#include
#include
#define pb push_back
using namespace std;
typedef pair<int,int> abcd;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

const int N=50005;
set Set;
struct edge{
  int u,v,next;
}G[N<<2];
int head[N],inum=1;
int cur[N];
inline void add(int u,int v,int p){
  G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p;
}
inline void Add(int u,int v){
  if (u>v) swap(u,v); if (!Set.count(abcd(u,v))) add(u,v,++inum),add(v,u,++inum),Set.insert(abcd(u,v));
}
#define V G[p].v

int n,m,cnt;
int cir[N<<2],depth[N],fap[N],fat[N];
inline void dfs(int u,int fa){
  depth[u]=depth[fa]+1; fat[u]=fa;
  for (int p=head[u];p;p=G[p].next)
    if (V!=fa)
      if (!depth[V])
    fap[V]=p,dfs(V,u);
      else if (depth[V]int t=u; ++cnt;
    while (t!=V) cir[fap[t]]=cir[fap[t]^1]=cnt,t=fat[t];
    cir[p]=cir[p^1]=cnt;
      }
}

int del[N<<2];

struct info{
  char f; int x,y,z;
  info(char f,int x,int y,int z=0):f(f),x(x),y(y),z(z) { }
};
vector Ans;

#define J(x,y) (Ans.pb(info('j',x,y)))
#define R(x,y,z) (Ans.pb(info('r',x,y,z)))
#define C(x,y,z) (Ans.pb(info('c',x,y,z)))

inline void Solve(int u){
  int ed=0;
  for (int p=cur[u];p;p=G[p].next)
    if (!del[p]){
      ed=p; break;
    }
  cur[u]=ed;
  if (!ed) return;
  del[ed]=del[ed^1]=1;
  int v=G[ed].v;
  if (!cir[ed]){
    Solve(u); Solve(v);
    R(v,1,3); J(u,v); C(u,1,3); R(u,3,2);
    return;
  }
  vector<int> path;
  path.pb(u); path.pb(v); int cur=v;
  while (1){
    int p;
    for (p=head[cur];p;p=G[p].next)
      if (cir[p]==cir[ed] && !del[p])
    break;
    del[p]=del[p^1]=1;
    if (V==u) break;
    path.pb(V); cur=V;
  }
  for (int x:path)
    Solve(x);
  R(v,1,3); J(u,v); C(u,1,3);
  int last=v;
  for (int i=2;i<(int)path.size();i++){
    int x=path[i];
    R(x,1,4); J(last,x); C(x,3,4); R(x,3,2); R(x,4,3);
    last=x;
  }
  C(u,1,3); R(u,3,2);
}

int main(){
  int x,y,k;
  freopen("cactus.in","r",stdin);
  freopen("cactus.out","w",stdout);
  read(n); read(m);
  while (m--){
    read(k); read(x);
    for (int i=2;i<=k;i++)
      read(y),Add(x,y),x=y;
  }
  dfs(1,0);
  for (int i=1;i<=n;i++) cur[i]=head[i];
  Solve(1);
  printf("%d\n",(int)Ans.size());
  for (info x:Ans)
    if (x.f=='j')
      printf("%c %d %d\n",x.f,x.x,x.y);
    else
      printf("%c %d %d %d\n",x.f,x.x,x.y,x.z);
  return 0;
}

推荐阅读
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文探讨了 Objective-C 中的一些重要语法特性,包括 goto 语句、块(block)的使用、访问修饰符以及属性管理等。通过实例代码和详细解释,帮助开发者更好地理解和应用这些特性。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • ImmutableX Poised to Pioneer Web3 Gaming Revolution
    ImmutableX is set to spearhead the evolution of Web3 gaming, with its innovative technologies and strategic partnerships driving significant advancements in the industry. ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 本题涉及一棵由N个节点组成的树(共有N-1条边),初始时所有节点均为白色。题目要求处理两种操作:一是改变某个节点的颜色(从白变黑或从黑变白);二是查询从根节点到指定节点路径上的第一个黑色节点,若无则输出-1。 ... [详细]
  • MySQL索引详解与优化
    本文深入探讨了MySQL中的索引机制,包括索引的基本概念、优势与劣势、分类及其实现原理,并详细介绍了索引的使用场景和优化技巧。通过具体示例,帮助读者更好地理解和应用索引以提升数据库性能。 ... [详细]
author-avatar
changeverything77_262
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有