Submission #229224

#	Time	Username	Problem	Language	Result	Execution time	Memory
229224		VEGAnn	Checker (COCI19_checker)	C++14	110 / 110	277 ms	43140 KiB

checker

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define MP make_pair
#define MP3(a, b, c) MP(MP(a, b), c)
#define PB push_back
#define all(x) x.begin(),x.end()
#define pii pair<int, int>
#define piis pair<pii, string>
#define ft first
#define sd second
using namespace std;
const int N = 200100;
unordered_map<int, int> rib[N];
string s;
int x[N], y[N], z[N], n, fen[N], nm[N], len[N], nt[N], pr[N], sta[N], ed[N];

void update(int ps, int vl){
	for (; ps < N; ps = (ps | (ps + 1)))
		fen[ps] += vl;
}

int sum(int ps){
	int res = 0;
	
	for (; ps >= 0; ps = (ps & (ps + 1)) - 1)
		res += fen[ps];
	
	return res;
}

bool cmp1(int _x, int _y){
	return (y[_x] - x[_x]) < (y[_y] - x[_y]);
}

bool cmp(int _x, int _y){
	return len[_x] < len[_y];
}

int MEX(int x, int y){
	return 3 - (x + y);
}

int main(){
	
	ios_base::sync_with_stdio(0); cin.tie(0);
	
//	freopen("in.txt","r",stdin); 
	
	cin >> n >> n;
	
	cin >> s;
	
	for (int i = 0; i < n - 3; i++){
		cin >> x[i] >> y[i] >> z[i];
		x[i]--; y[i]--; z[i]--;
		
		if (x[i] > y[i]) swap(x[i], y[i]);
		
		len[i] = min(y[i] - x[i], n - (y[i] - x[i]));
		
		nm[i] = i;
	}
	
	sort(nm, nm + n - 3, cmp1);
	
	for (int it = 0; it < n - 3; it++) {
			
		int i = nm[it];
						
		if (sum(y[i]) - sum(x[i] - 1) - sta[y[i]] + ed[x[i]] != 0){
			cout << "neispravna triangulacija";
			return 0;
		}
		
		update(x[i], 1);
		update(y[i], -1);
		
		sta[x[i]]++;
		ed[y[i]]++;
	}
		
	sort(nm, nm + n - 3, cmp);
	
	for (int i = 0; i < n; i++){
		nt[i] = (i + 1) % n;
		pr[i] = (i - 1 + n) % n;
		
		rib[i][nt[i]] = (s[i] - '1');
	}
	
	
	for (int it = 0; it < n - 3; it++){
		int i = nm[it];
				
		int pro = nt[x[i]];
		
		if (nt[pro] != y[i]){
			swap(x[i], y[i]);
			
			pro = nt[x[i]];
		}
		
		if (MEX(rib[x[i]][pro], rib[pro][y[i]]) != z[i]){
			cout << "neispravno bojenje";
			return 0;
		}
		
		nt[x[i]] = y[i];
		pr[y[i]] = x[i];
	
		rib[x[i]][y[i]] = z[i];
	}
	
	cout << "tocno";
	
	return 0;
}

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