首页 > 代码库 > UVALIVE 2686 Stargates

UVALIVE 2686 Stargates

尼玛真深坑合时p[x] = y 就RE,p[y] = x 就AC 、

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 6066010int p[MAXN];int Find(int x) { return x == p[x] ? x : p[x] = Find(p[x]);}char op;char res[100];int src,des,nnn,srcstep,desstep;int read(char *res){    int cnt = 0, cas = 0;    for (int i = 1; i < strlen(res); i++)        if (res[i] !=   && res[i - 1] ==  ) cnt++;    return cnt;}int main(){    while (gets(res))    {        op = tolower(res[0]);        int N;        if (op == d) {sscanf(res,"%*s %d",&N);for (int i = 0; i <= N; i++)  p[i] = i; continue;}        int cnt = read(res);        if (cnt == 2)        {            sscanf(res,"%*s %d %d",&src,&des);            nnn = 1;            srcstep = 0; desstep = 0;        }        if (cnt == 3)        {            sscanf(res,"%*s %d %d %d",&src,&des,&nnn);            srcstep = 0;            desstep = 1;        }        if (cnt == 4)        {            sscanf(res,"%*s %d %d %d %d",&src,&des,&nnn,&desstep);            srcstep = 0;        }        if (cnt == 5)        {            sscanf(res,"%*s %d %d %d %d %d",&src,&des,&nnn,&desstep,&srcstep);        }        if (op == c){            if (srcstep == 0 && desstep==0)nnn=1;            for (int i = src , j = des, k = 0; k < nnn; i += srcstep,j += desstep,k++)            {                int  x = Find(i) , y = Find(j);                 p[y] = x;            }        }        else        {            int ansl = 0 ,ansr = 0;            for (int i = src , j = des, k = 0; k < nnn; i += srcstep,j += desstep,k++)            {                int  x = Find(i) , y = Find(j);                if (x != y) ansr++;                else ansl++;            }            printf("%d - %d\n",ansl,ansr);        }    }    return 0;}

 

UVALIVE 2686 Stargates