oj.uz

Submission #531508

# Submission time Handle Problem Language Result Execution time Memory
531508 2022-03-01T00:37:27 Z colazcy Dijamant (COI16_dijament) C++17
100 / 100
 336 ms 4700 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 332 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 3364 KB Output is correct
2 Correct 336 ms 4700 KB Output is correct
3 Correct 67 ms 4532 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 456 KB Output is correct
6 Correct 7 ms 516 KB Output is correct
7 Correct 13 ms 588 KB Output is correct
8 Correct 25 ms 716 KB Output is correct
9 Correct 38 ms 820 KB Output is correct
10 Correct 6 ms 452 KB Output is correct
11 Correct 4 ms 440 KB Output is correct
12 Correct 281 ms 3844 KB Output is correct