Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
complexity
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 120
using namespace std;
typedef struct
{
int t;
int i;
int x;
int y;
}COMMAND;
char s[N];
int l, f;
COMMAND a[N];
int t[N], g[N], h[N];
bool u[N];
bool Parse(void)
{
int i, c;
for(i = c = 0;i < l;i ++)
if(a[i].t)
{
c --;
if(c < 0)
return false;
}
else
c ++;
if(c)
return false;
memset(t, 0, sizeof(t));
memset(g, 0, sizeof(g));
memset(h, 0, sizeof(h));
memset(u, false, sizeof(u));
for(i = c = 0;i < l;i ++)
if(a[i].t)
{
c --;
u[a[t[c]].i] = false;
g[t[c]] = i;
h[i] = t[c];
}
else
{
if(u[a[i].i])
return false;
u[a[i].i] = true;
t[c ++] = i;
}
return true;
}
void Solve(void)
{
int i, c, o;
scanf("%d %s", &l, s);
if(s[2] == '1')
f = 0;
else
sscanf(s + 4, "%d", &f);
for(i = 0;i < l;i ++)
{
scanf("%s", s);
if(s[0] == 'F')
{
a[i].t = 0;
scanf("%s", s);
a[i].i = s[0] - 'a';
scanf("%s", s);
if(s[0] == 'n')
a[i].x = N;
else
sscanf(s, "%d", &a[i].x);
scanf("%s", s);
if(s[0] == 'n')
a[i].y = N;
else
sscanf(s, "%d", &a[i].y);
}
else if(s[0] == 'E')
a[i].t = 1;
else
{
gets(s);
l --;
i --;
}
}
if(!Parse())
{
puts("ERR");
return;
}
memset(u, false, sizeof(u));
for(i = o = c = 0;i < l;i ++)
{
if(a[i].t)
{
if(u[h[i]])
c --;
}
else
{
if(a[i].x == N && a[i].y == N)
;
else if(a[i].x == N && a[i].y != N)
i = g[i];
else if(a[i].x != N && a[i].y == N)
{
c ++;
u[i] = true;
o = max(o, c);
}
else
{
if(a[i].x > a[i].y)
i = g[i];
}
}
//printf("line %d, c = %d\n", i, c);
}
puts(o == f ? "Yes" : "No");
return;
}
int main() //complexity.cpp
{
int t;
freopen("complexity.in" , "r", stdin );
freopen("complexity.out", "w", stdout);
scanf("%d", &t);
while(t --)
Solve();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.