Submission #444704

#	Time	Username	Problem	Language	Result	Execution time	Memory
444704		penguinhacker	Checker (COCI19_checker)	C++14	110 / 110	720 ms	95892 KiB

checker

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

#define ll long long
#define ar array

const int mxN=2e5;
int n;
string s;
ar<int, 3> e[mxN];

set<ar<ll, 2>> seen;
vector<int> f[mxN];
int l[mxN];
multiset<int> seg;

set<ar<int, 2>> adj[mxN];
int tr;

void add(int i, int j, int c) {
	adj[i].insert({j, c});
	adj[j].insert({i, c});
}

set<ar<int, 2>>::iterator gt(int i, int j) {
	auto it=adj[i].lower_bound({j});
	assert(it!=adj[i].end()&&(*it)[0]==j);
	return it;
}

void rem(int u) {
	++tr;
	int i=(*adj[u].begin())[0], j=(*adj[u].rbegin())[0];
	int c1=(*adj[u].begin())[1], c2=(*adj[u].rbegin())[1];
	adj[u].clear();
	adj[i].erase(gt(i, u));
	adj[j].erase(gt(j, u));
	gt(i, j);
	int c3=(*gt(j, i))[1];
	if (c1==c2||c1==c3||c2==c3) {
		cout << "neispravno bojenje";
		exit(0);
	}
	if (adj[i].size()==2)
		rem(i);
	if (adj[j].size()==2)
		rem(j);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> n >> s;
	for (int i=0; i<n-3; ++i) {
		cin >> e[i][0] >> e[i][1] >> e[i][2], --e[i][0], --e[i][1];
		if (e[i][0]>e[i][1])
			swap(e[i][0], e[i][1]);
		if (seen.count({e[i][0], e[i][1]})) { // double edge??? bad..
			cout << "neispravna triangulacija";
			return 0;
		}
		seen.insert({e[i][0], e[i][1]});
		f[e[i][0]].push_back(e[i][1]);
		++l[e[i][1]];
	}
	for (int i=0; i<n; ++i) {
		while(l[i]--) {
			auto it=seg.find(i);
			assert(it!=seg.end());
			seg.erase(it);
		}
		assert(seg.empty()||*seg.begin()>i);
		for (int j : f[i])
			if (seg.size()&&j>*seg.begin()) {
				cout << "neispravna triangulacija";
				return 0;
			}
		for (int j : f[i])
			seg.insert(j);
	}
	for (int i=0; i<n; ++i)
		add(i, (i+1)%n, s[i]-'0');
	for (int i=0; i<n-3; ++i)
		add(e[i][0], e[i][1], e[i][2]);
	for (int i=0; i<n; ++i)
		if (adj[i].size()==2)
			rem(i);
	assert(tr==n-2);
	cout << "tocno";
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35