Codeforces Round #199 (Div. 2) E. Xenia and Tree

제목 링크
2. 하마터면 A 가 될 뻔 했 어 요...이 문 제 는 정말 어렵 지 않 습 니 다. 처음에 생각 한 것 은 폭력 spfa 면 됩 니 다. 직접 와 서 물 어보 면 한 번 오 는 것 입 니 다. TLE 입 니 다. 생각해 보 니 창고 에 저장 하 는 것 이 더 빠 르 고 TLE 를 다시 제출 할 수 있 을 것 같 습 니 다.어 쩔 수 없 이 C 가 또 cha 를 당 했 어 요. 저 는 C 를 보 러 갔 어 요...이 문 제 는 내 가 한 곳 에서 잘못 썼 다.top = 0 일 때 죽 어 요?안 할 것 같 아 요. 어쨌든 제 가 이 판단 을 넣 었 으 니 A 예요. 최 적 화 했 나 봐 요.

 1 #include <cstring>

 2 #include <cstdio>

 3 #include <string>

 4 #include <iostream>

 5 #include <algorithm>

 6 #include <cmath>

 7 #include <queue>

 8 using namespace std;

 9 #define INF 1000000

10 int first[200001];

11 int dis[200001];

12 int in[200001];

13 int s[200001];

14 int n,t,top;

15 struct node

16 {

17     int u,v,next;

18 }edge[300001];

19 void CL()

20 {

21     t = 0;

22     memset(first,-1,sizeof(first));

23 }

24 void add(int u,int v)

25 {

26     edge[t].u = u;

27     edge[t].v = v;

28     edge[t].next = first[u];

29     first[u] = t ++;

30 }

31 void spfa()

32 {

33     int i,u,v;

34     for(i = 1;i <= n;i ++)

35     in[i] = 0;

36     queue<int>que;

37     for(i = 0;i < top;i ++)

38     {

39         in[s[i]] = 1;

40         dis[s[i]] = 0;

41         que.push(s[i]);

42     }

43     while(!que.empty())

44     {

45         u = que.front();

46         que.pop();

47         in[u] = 0;

48         for(i = first[u];i != -1;i = edge[i].next)

49         {

50             v = edge[i].v;

51             if(dis[v] > dis[u] + 1)

52             {

53                 dis[v] = dis[u] + 1;

54                 if(!in[v])

55                 {

56                     in[v] = 1;

57                     que.push(v);

58                 }

59             }

60         }

61     }

62     return ;

63 }

64 int main()

65 {

66     int m,i,u,v;

67     CL();

68     scanf("%d%d",&n,&m);

69     for(i = 1;i < n;i ++)

70     {

71         scanf("%d%d",&u,&v);

72         add(u,v);

73         add(v,u);

74     }

75     for(i = 1;i <= n;i ++)

76     dis[i] = INF;

77     top = 1;

78     s[0] = 1;

79     spfa();

80     top = 0;

81     for(i = 1;i <= m;i ++)

82     {

83         scanf("%d%d",&u,&v);

84         if(u == 1)

85         {

86             s[top ++] = v;

87         }

88         else

89         {

90             if(top != 0)//  

91             spfa();

92             top = 0;

93             printf("%d
",dis[v]);

94         }

95     }

96     return 0;

97 }