表示戴第a 号面具的人探望了第b 号面具的编号

1064: [Noi2008]假面舞会

Time Limit: 10 Sec  Memory
Limit: 162 MB

Description

  一年一度的假面晚会又开始了,栋栋也兴致勃勃的到位了现年的晚上的集会。二零一八年的面具都以主办方极度定制的。每一个加入晚会的人都得以在登场时选用贰个本身喜好的面具。每种面具都有叁个编号,主办方会把此号码告诉拿该面具的人。为了使晚会更有神秘感,主办方把面具分为k
(k≥3)类,并行使非常的技巧将各样面具的数码标在了面具上,唯有戴第i
类面具的人才具收看戴第i+1 类面具的人的号码,戴第k 类面具的人能见到戴第1
类面具的人的号子。
加入晚会的人并不知道有微微类面具,然则栋栋对此却极其愕然,他想自个儿算出有多少类面具,于是他开首在人群中收罗音讯。
栋栋搜聚的音信都以戴第几号面具的人见状了第几号面具的数码。如戴第2号面具的人看出了第5
号面具的编号。栋栋自个儿也会看出部分数码,他也会依靠本身的面具编号把音信补充进去。由于并不是各样人都能记住本身所见到的全体数码,由此,栋栋采集的信息不可能担保其完整性。现在请您计算,遵照栋栋近日到手的音讯,至多和至少有多少类面具。由于主办方已经宣示了k≥3,所以你必须将那条音讯也挂念进去。

Input

  第一行李包裹蕴多少个整数n,
m,用两个空格分隔,n 表示主办方总共图谋了稍稍个面具,m
代表栋栋采撷了略微条音信。接下来m 行,每行为四个用空格分开的莫西干发型a,
b,表示戴第a 号面具的人见到了第b 号面具的号码。一样的数对a, b
在输入文件中大概出现屡屡。

Output

  包蕴七个数,第二个数为最大或然的面具类数,第3个数为最小恐怕的面具类数。假若不可能将有所的面具分为至少3
类,使得这个音信都满足,则以为栋栋搜聚的音讯有错误,输出三个-1。

Sample Input

【输入样例一】
6 5
1 2
2 3
3 4
4 1
3 5
【输入样例二】
3 3
1 2
2 1
2 3

Sample Output

【输出样例一】
4 4
【输出样例二】
-1 -1

HINT

100%的数据,满足n ≤ 100000, m ≤
1000000。

 

  来自于图论之神QT的联赛模拟题……考试的场合上没想清楚多少个出口写挂了,好在namespace了三个暴力。

  还好QT给了壹个人心样例,让自个儿意识了有的了不可的业务。

  暴力是枚举答案染色check。那么对王宛平解,肯定是图中的环的深浅的gcd。可是恐怕无休止唯有环这种状态,恐怕有“伪环”,即眼下深度为10的连向深度为4的,那么就有多少个高低为6的环。

  把边和反向边的边权分别设为1和-1,对于每二个点访问叁回,更新与它不断的点。全数望深度压进一个点的vector里面,最终sort一下各种vector,里面包车型客车数之差就对应着三个环的大大小小。对那些数取叁个gcd就足以了。

  三种独特境况:答案是1,2要出口-1、完全没有环要输出每一种联通块最长链之和。

  依旧有一些难度的题,要不是样例大概摸不到边。

图片 1图片 2

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#define LL long long
#define rg register
#define FILE "party"
using namespace std;

const int N = 100010;
struct Node{int to,next;}E[N*20],Er[N*20];
int n,m,head[N],tot,Head[N],Tot;
int col[N],vis[N],Ans1=-1,Ans2=-1;
int bin[N],Mxc,Mic,Jc,chain;
vector<int>G[N],W[N];

inline int gi(){
  rg int x=0,res=1;rg char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-')res^=1;ch=getchar();}
  while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
  return res?x:-x;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
  Er[++Tot]=(Node){u,Head[v]};
  Head[v]=Tot;
}

inline int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}

namespace cheat{
  inline void xr(int x,int c){
    vis[x]=1;G[x].push_back(c);
    Mxc=max(c,Mxc);Mic=min(Mic,c);
    for(int e=head[x];e;e=E[e].next){
      int y=E[e].to;
      if(vis[y])G[y].push_back(c+1);
      else xr(y,c+1);
    }
    for(int e=Head[x];e;e=Er[e].next){
      int y=Er[e].to;
      if(vis[y])G[y].push_back(c-1);
      else xr(y,c-1);
    }
  }

  inline int clr(int x,int tp=0){
    for(int i=0,j=G[x].size();i<j;++i)
      bin[++tp]=G[x][i];
    if(!tp)return false;
    sort(bin+1,bin+tp+1);
    tp=unique(bin+1,bin+tp+1)-bin-1;
    if(tp==1)return false;
    for(int i=1;i<=tp;++i)
      W[x].push_back(bin[i]);
    return true;
  }

  inline int calc(int x,int ans=0){
    for(int i=1,j=W[x].size();i<j;++i){
      ans=gcd(ans,W[x][i]-W[x][i-1]);
    }
    return ans;
  }

  inline int work(int x){
    for(int i=3;i<=x;++i)
      if(x%i==0)return i;
    return x;
  }

  int mian(){
    for(int i=1;i<=n;++i)
      if(!vis[i]){
        Mxc=Mic=1;
        xr(i,1);
        chain+=(Mxc-Mic+1);
      }
    int flg=0,Ans=0;
    for(int i=1;i<=n;++i)
      if(clr(i))
        Ans=gcd(Ans,calc(i)),flg=1;
    if(!flg){
      if(chain>2)cout<<chain<<' '<<3<<endl;
      else cout<<"-1 -1\n";
    }
    else{
      if(Ans>2)cout<<Ans<<' '<<work(Ans)<<endl;
      else cout<<"-1 -1\n";
    }
    return 0;
  }
}

int main(){
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  n=gi();m=gi();
  for(int i=1;i<=m;++i){
    int u=gi(),v=gi();
    link(u,v);
  }
  return cheat::mian();
  fclose(stdin);fclose(stdout);
  return 0;
}

假面晚会

 

相关文章

网站地图xml地图