27分RE
查看原帖
27分RE
377768
Tooler_Yang楼主2022/10/14 21:00
// Problem: P3952 [NOIP2017 提高组] 时间复杂度
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3952
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

struct bian{
	string name;
	string from;
	string to;
	int gv;
};
set<string> mp;
stack<bian> t;
int o(string s){
	if(s[2]=='1') return 0;
	else{
		
		stack<int> k;
		int w=0;
		for(int i=4;i<s.size()-1;i++){
			if(s[i]!=')'){
				k.push(s[i]-'0');
			}
		}
		while(!k.empty()){
			w*=10;
			w+=k.top();
			k.pop();
		}
		return w;
	}
}
void gett(string s){
	int now=0;
	string nm[3]={"","",""}; 
	for(int i=2;i<s.size();i++){
		if(s[i]!=' '){
			nm[now]+=s[i];
		}
		else{
			now++;
		}
	}
	bian ps;
	ps.name=nm[0];
	ps.from=nm[1];
	ps.to=nm[2];
	ps.gv=0;
	t.push(ps);
}
void chu(bian x){
	string a=x.from;
	string b=x.to;
	int fm=0,To=0;
	if(a[0]<='9'&&a[0]>='0'){
		stack<int> k;
		for(int i=0;i<a.size();i++){
			k.push(a[i]-'0');
		}
		while(!k.empty()){
			fm*=10;
			fm+=k.top();
			k.pop();
		}
	}
	else{
		fm=0x3f3f3f3f;
	}
	if(b[0]<='9'&&b[0]>='0'){
		stack<int> k;
		for(int i=0;i<b.size();i++){
			k.push(b[i]-'0');
		}
		while(!k.empty()){
			To*=10;
			To+=k.top();
			k.pop();
		}
	}
	else{
		To=0x3f3f3f3f;
	}
	if(To==0x3f3f3f3f){
		if(fm==0x3f3f3f3f){
			t.top().gv=0;
		}
		else{
			t.top().gv=1;
		}
	}
	else{
		if(To<fm){
			t.top().gv=-1;
		}
		else{
			t.top().gv=0;
		}
	}
}
string s[101];
int main(){
	
	int T;
	cin>>T;
	while(T--){
		while(!t.empty()){
			t.pop();
		}
		int n;
		scanf("%d ",&n);
		string O;
		getline(cin,O);
		int ww=o(O);
		for(int i=1;i<=n;i++){
			getline(cin,s[i]);
		}
		int ans=0xc0c0c0c0;
		int w=0;
		
		bool flag=false;
		mp.clear();
		for(int i=1;i<=n;i++){
			if(s[i][0]=='F'){
				gett(s[i]);
				chu(t.top());
				int sz1=mp.size();
				mp.insert(t.top().name);
				int sz2=mp.size();
				if(sz1==sz2){
					ans=0xc0c0c0c0;
					break;
				}
				if(t.top().gv==-1){
					flag=true;
				}
			}
			else{
				mp.erase(t.top().name);
				if(!flag){
					w+=t.top().gv;
				}
				if(t.top().gv==-1){
					flag=false;
				}
				
				t.pop();
			}
			if(t.empty()){
				ans=max(ans,w);
				w=0;
			}
			// cout<<w<<" "<<ans<<"\n";
		}
		if(ans==0xc0c0c0c0){
			cout<<"ERR\n";
		}
		else if(ans==ww){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}
		// cout<<ans<<"\n";
	}
	return 0;
}
2022/10/14 21:00
加载中...