热门标签 | 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;
}

推荐阅读
  • 本题探讨了一种字符串变换方法,旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量,从而确定转换的可能性。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]
  • Java 中 Writer flush()方法,示例 ... [详细]
  • 主要用了2个类来实现的,话不多说,直接看运行结果,然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]
  • DNN Community 和 Professional 版本的主要差异
    本文详细解析了 DotNetNuke (DNN) 的两种主要版本:Community 和 Professional。通过对比两者的功能和附加组件,帮助用户选择最适合其需求的版本。 ... [详细]
  • 本文探讨了 Objective-C 中的一些重要语法特性,包括 goto 语句、块(block)的使用、访问修饰符以及属性管理等。通过实例代码和详细解释,帮助开发者更好地理解和应用这些特性。 ... [详细]
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社区 版权所有