澳门1495

BZOJ 1064 假面舞会。BZOJ 1064 假面舞会。

九月 27th, 2018  |  综合体育

1064: [Noi2008]假面舞会

Time Limit: 10 Sec  Memory
Limit: 162 MB

1064: [Noi2008]假面舞会

Time Limit: 10 Sec  Memory
Limit: 162 MB

Description

  一年一度的假面舞会又起了,栋所呢兴致勃勃的到了今年之舞会。今年底面具都是主办方特别定制的。每个参加舞会的人数还得于入场时选一样
个祥和喜爱的面具。每个面具都有一个码,主办方会把这号码告诉拿该面具的人口。为了要舞会更产生神秘感,主办方将面具分为k
(k≥3)类,并使特别之艺以每个面具的号码标以了面具上,只来戴第i
类面具的人口才能够看戴第i+1 类面具的口的号码,戴第k 类面具的丁能够观看戴第1
类面具的总人口之数码。
参加舞会的人头并不知道有略类似面具,但是栋栋对是却专门怪,他思念协调毕竟有有略类似面具,于是他开当人群面临收集信息。
栋栋收集之信息还是戴第几如泣如诉面具的人数看来了第几哀号面具的号。如戴第2号面具的丁张了第5
号面具的号。栋栋好为会看有号码,他也会基于自己的面具编号把信补充进。由于并无是每个人都能记住好所看到底布满号码,因此,栋栋收集的信
息不可知管其完整性。现在恳请您算,按照所幢目前赢得的信,至多同至少发生稍许类似面具。由于主办方都宣称了k≥3,所以你不能不用即时漫长信息也设想进来。

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
在输入文件中恐怕出现反复。

Input

  第一实施包含两只整数n,
m,用一个空格分隔,n 代表主办方共准备了有些个面具,m
表示栋栋收集了不怎么条消息。接下来m 行,每行为寡独用空格分开的整数a,
b,表示戴第a 号面具的总人口看出了第b 号面具的号子。相同之数对a, b
在输入文件中或出现频。

Output

  包含两只数,第一个数为无限酷或的面具类数,第二个数为极其小莫不的面具类数。如果无法用具备的面具分为至少3
类,使得这些消息还满足,则当栋栋收集之音讯发误,输出两单-1。

Output

  包含两独数,第一个数为无限老可能的面具类数,第二个数为极端小或者的面具类数。如果无法将持有的面具分为至少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 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

Sample Output

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

HINT

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

 

  来自于图论之神QT的联赛模拟题……考场上尚未想明白几单出口写挂了,幸好namespace了一个强力。

  好当QT给了一个灵魂样例,让自己发现了部分了不足的作业。

  暴力是枚举答案染色check。那么对正解,肯定是祈求被之拱卫的分寸的gcd1495娱乐。但是可能不断只发生环这种状态,可能有“伪环”,即当前深度为10之并于纵深为4的,那么即便产生一个分寸也6的缠绕。

  将边与反往无尽的边权分别要为1暨-1,对于各级一个碰看同一不行,更新和她不止的接触。所有或深度压进一个碰的vector里面,最后sort一下每个vector,里面的高频之异就针对诺在一个圈的深浅。对这些数取一个gcd就可了。

  几栽异常状况:答案是1,2比方出口-1、完全无环要输出每个联通片最丰富链之和。

  还是生硌难度之开,要无是样例可能找不顶边。

1495娱乐 11495娱乐 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;
}

假面舞会

 

HINT

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

 

  来自于图论之神QT的联赛模拟题……考场上尚未想明白几单出口写挂了,幸好namespace了一个强力。

  好于QT给了一个灵魂样例,让自己发觉了有了不足的事情。

  暴力是枚举答案染色check。那么对正解,肯定是祈求备受之环绕的分寸的gcd。但是可能不断只生环这种状态,可能出“伪环”,即当前深度为10之并为深度为4的,那么就是出一个高低为6之围。

  把边和倒朝无尽的边权分别要为1跟-1,对于各级一个沾访问同不行,更新与她不断的点。所有可能深度压进一个触及的vector里面,最后sort一下每个vector,里面的一再的异就对准诺在一个圈的深浅。对这些数取一个gcd就可以了。

  几种植新鲜情况:答案是1,2要是出口-1、完全无环要输出每个联通块最丰富链之和。

  还是发生接触难度的书写,要无是样例可能找不交边。

1495娱乐 31495娱乐 4

#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;
}

假面舞会

 

相关文章

标签:, , ,

Your Comments

近期评论

    功能


    网站地图xml地图