Submission #531508

#	Time	Username	Problem	Language	Result	Execution time	Memory
531508		colazcy	Dijamant (COI16_dijament)	C++17	100 / 100	336 ms	4700 KiB

dijament

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <cassert>
#include <bitset>
#include <vector>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 1003;


int n,tot;
std::map<std::string,int> mp;
std::string readToken(){
	std::string res;
	std::cin >> res;
	return res;
}
std::bitset<maxn> f[maxn];
bool find(const std::vector<int> &vec,const int x){
	let it = std::lower_bound(vec.begin(),vec.end(),x);
	if(it == vec.end())return false;
	return *it == x;
}
int main(){
	// std::freopen("dijamant.in","r",stdin);
	// std::freopen("dijamant.out","w",stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n;
	rep(id,1,n){
		let now = readToken();
		readToken();
		std::vector<std::string> base;
		while(true){
			let t = readToken();
			if(t == ";")break;
			base.push_back(t);
		}
		if(mp[now]){
			std::cout << "greska\n";
			continue;
		}
		bool flg = true;
		for(let &t : base)
			if(!mp[t]){
				flg = false;
				break;
			}
		if(!flg){
			std::cout << "greska\n";
			continue;
		}

		using type = std::pair<int,int>;
		std::vector<type> vec;
		for(let &x : base)vec.emplace_back(f[mp[x]].count(),mp[x]);
		std::sort(vec.begin(),vec.end(),[](const type &lhs,const type &rhs){
			return lhs.first > rhs.first;
		});
		
		std::bitset<maxn> s;
		for(let &x : vec){
			if(s.test(x.second))continue;
			if((s & f[x.second]).any()){
				flg = false;
				break;
			}
			s |= f[x.second];
		}
		
		if(!flg){
			std::cout << "greska\n";
			continue;
		}
		mp[now] = ++tot;
		for(let &x : base)s |= f[mp[x]];
		f[tot] = s;
		f[tot].set(tot);
		
		std::cout << "ok\n";
	}
	// std::fclose(stdin);
	// std::fclose(stdout);
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44