UVALive 6953 Digi Comp II

​​點選打開連結​​

#include<cstdio>
#include<ctime>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 500015;
LL n, sum[maxn], T, m, flag[maxn], in[maxn];
int L[maxn], R[maxn];
char s[8];

int main()
{
  while (cin >> n >> m)
  {
    for (int i = 0; i <= m; i++) sum[i] = in[i] = 0;
    for (int i = 1; i <= m; i++)
    {
      scanf("%s%d%d", s, &L[i], &R[i]);
      flag[i] = s[0] == 'L' ? 1 : 0;
      ++in[L[i]]; ++in[R[i]];
    }
    queue<int> p;
    for (int i = 1; i <= m; i++) if (!in[i]) p.push(i);
    sum[1] = n;
    while (!p.empty())
    {
      int q = p.front();  p.pop();
      if (L[q])
      {
        if (--in[L[q]] == 0) p.push(L[q]);
        sum[L[q]] += (sum[q] + flag[q]) >> 1;
      }
      if (R[q])
      {
        if (--in[R[q]] == 0) p.push(R[q]);
        sum[R[q]] += (sum[q] + 1 - flag[q]) >> 1;
      }
      flag[q] ^= (sum[q] & 1);
    }
    for (int i = 1; i <= m; i++)
      if (flag[i]) putchar('L'); else putchar('R');
    putchar(10);
  }
  return 0;
}