TOJ 2551 Stargates

 1 /*
 2  * File:   F.cpp
 3  * Author: GongZhi
 4  *
 5  * Created on 2009年7月27日, 下午12:19
 6  */
 7 
 8 #include <stdlib.h>
 9 #include <string.h>
10 #include <stdio.h>
11 /*
12  *
13  */
14 const int MAX = 6100000;
15 int uset[MAX];
16 int n;
17 int root(int k) {
18     int t = k;
19     while (uset[t] != t)
20         t = uset[t];
21     while (uset[k] != k) {
22         int p = uset[k];
23         uset[k] = t;
24         k = p;
25     }
26     return uset[k];
27 }
28 
29 int init(int n) {
30     for (int i = 0; i <= n; ++i)
31         uset[i] = i;
32     return 0;
33 }
34 
35 int query(int src, int dst, int ss, int ds, int nnn) {
36     int ans=0;
37     for (int i = 0; src<=&& dst<=&& i < nnn; ++i) {
38         int a = root(src);
39         int b = root(dst);
40         if (a == b)
41             ++ans;
42         src += ss;
43         dst += ds;
44     }
45     printf("%d - %d\n", ans, nnn - ans);
46     return 0;
47 }
48 
49 int join(int src, int dst, int ss, int ds, int nnn) {
50     int ans = 0;
51     for (int i = 0; src<=&& dst<=&& i < nnn; ++i) {
52         int a = src;//root(src);
53         int b = root(dst);
54         uset[b] = a;
55         src += ss;
56         dst += ds;
57     }
58     return 0;
59 }
60 
61 int get(char* s)
62 {
63     int i=0;
64     char c;
65     while(true)
66     {
67         c=getchar();
68         if(c==-1)return -1;
69         if(c=='\n')break;
70         s[i]=c;
71         ++i;
72     }
73     s[i]=0;
74     return 1;
75 }
76 
77 int main(int argc, char** argv) {
78     char line[1024];
79     //freopen("in.txt","r",stdin);
80     while (gets(line)!=NULL) {
81         int src = 0, dst = 0;
82         int nnn = 1, ss = 0, ds = 1;
83         char tmp[100];
84         if (line[0== 'D' || line[0== 'd') {
85             sscanf(line, "%s%d", tmp, &n);
86             init(n);
87         } else {
88             int i;
89             sscanf(line,"%s%d%d%d%d%d",tmp,&src,&dst,&nnn,&ds,&ss);
90             if (line[0== 'Q' || line[0== 'q')
91                 query(src, dst, ss, ds, nnn);
92             else
93                 join(src, dst, ss, ds, nnn);
94         }
95     }
96     return (EXIT_SUCCESS);
97 }
98 

posted on 2009-07-27 15:58 gong 阅读(926) 评论(1)  编辑 收藏 引用

评论

# re: TOJ 2551 Stargates 2009-07-28 15:20 个性艺术签名

这些从现在才  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜