/ tabris /

记录详情

Time Exceeded


  
# 状态 耗时 内存占用
#1 Wrong Answer 3ms 344.0 KiB
#2 Wrong Answer 3ms 368.0 KiB
#3 Wrong Answer 47ms 768.0 KiB
#4 Time Exceeded ≥2004ms ≥256.0 KiB
#5 Wrong Answer 12ms 576.0 KiB
#6 Wrong Answer 231ms 2.109 MiB

代码

#include <bits/stdc++.h>
using namespace std;

#define INF         (~(1<<31))
#define INFLL       (~(1ll<<63))
#define pb          push_back
#define mp          make_pair
#define abs(a)      ((a)>0?(a):-(a))
#define lalal       puts("*******");
#define s1(x)       scanf("%d",&x)
#define Rep(a,b,c)  for(int a=(b);a<=(c);a++)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
void fre(){
    freopen("test_in.txt","r",stdin);
    freopen("test_out.txt","w",stdout);
}
inline int read(){
    char ch = getchar();int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
/***********************************************************************/
string str[10]={"query","fight","tempt","revolt"};
int pre[N<<1],h[N],son[N<<1],cnt,ans;

int findi(int x){
    int r = x;
    while(r!=pre[r])  r=pre[r];

    int i = x,j;
    while(i!=r){
        j=pre[i];
        pre[i]=r;
        i=j;
    }

    return r;
}

void join(int x,int y){
    int fx = findi(h[x]),fy = findi(h[y]);
    int temp = ans;
    if(x==2&&y==3){
        printf("%d %d ",fx,fy);
        printf("%d %d\n",son[fx],son[fy]);
    }
    if(son[fx]<son[fy])  pre[fx]=fy,son[fy]+=son[fx],ans--,printf("%d",y);
    if(son[fy]<son[fx])  pre[fy]=fx,son[fx]+=son[fy],ans--,printf("%d",x);
    if(temp == ans) printf("Either");
    puts(" is winner!");
    return;
}

void creat(int now){
    h[now]=++cnt;
    pre[cnt]=cnt;
    son[cnt]=1;
    ans++;
}

int main(){
    ios::sync_with_stdio(false);
   // fre();

    int n,m,x,y,_=1,kcase = 0;
    cin>>_;
    while(_--){
        cin>>n>>m;
        cnt = 0,ans = 0;
        for(int i=1;i<=n;i++) creat(i);

        printf("Case #%d:\n",++kcase);
        while(m--){
           // for(int i=1;i<=n;i++)   printf("%d %d %d %d\n",i,h[i],pre[h[i]],findi(h[i]));

            cin>>str[4];
            if(str[4]==str[0]){//query
                printf("%d\n",ans);
            }
            else if(str[4]==str[1]){//fight
                cin>>x>>y;
                join(x,y);
            }
            else if(str[4]==str[2]){//tempt
                cin>>x>>y;
                int fx = findi(h[x]),fy = findi(h[y]);
                //printf("fx = %d  fy = %d\n",fx,fy);
                son[fy]--,son[fx]++;
                if(!son[fy]) ans--;
                creat(y);
                pre[h[y]]=fx;
                ans--;

                //printf("%d %d <-----\n",h[2],findi(h[2]));
                int r=h[2];
                while(r!=pre[r]){
                    //printf("%d ",r);
                    r=pre[r];
                }
                //printf("%d ",r);
                //puts("<--");

            }
            else if(str[4]==str[3]){//revolt
                cin>>x;
                int fx = findi(h[x]);
                son[fx]--;
                creat(x);
            }
            else {
                puts("So bad!");
            }
        }
    }
    return 0;
}

信息

递交者
类型
递交
题目
测试用
语言
C++
递交时间
2017-06-22 13:06:42
评测时间
2017-06-25 13:27:26
评测机
分数
0
总耗时
≥2302ms
峰值内存
≥2.109 MiB